Submission #1174457
Source Code Expand
using System; using System.Text; using System.Collections.Generic; class Solve{ public Solve(){} int N; StringBuilder sb; public static int Main(){ new Solve().Run(); return 0; } void Run(){ sb = new StringBuilder(); Calc(); Console.Write(sb.ToString()); } void Calc(){ N = int.Parse(Console.ReadLine()); string[] str = Console.ReadLine().Split(' '); long[] T = new long[N]; for(int i=0;i<N;i++){ T[i] = int.Parse(str[i]); } int M = int.Parse(Console.ReadLine()); for(int j=0;j<M;j++){ str = Console.ReadLine().Split(' '); long originalT = T[int.Parse(str[0])-1]; T[int.Parse(str[0])-1] = int.Parse(str[1]); long[] DP = new long[N]; long[] sum = new long[N]; sum = new long[N]; sum[0] = T[N-1]; for(int i=1;i<N;i++){ sum[i] = sum[i-1] + T[N-1-i]; } ConvexHullTrick Con = new ConvexHullTrick(N+1); Con.Add(-1,1); for(int i=0;i<N;i++){ DP[N-1-i] = Math.Max(i == 0 ? 0 : DP[N-i],Con.Query(-i)-sum[i]+i*(i+1)/2); Con.Add(i,DP[N-1-i]+sum[i]+i*(i-1)/2); } sb.Append(DP[0]+"\n"); T[int.Parse(str[0])-1] = originalT; } } } struct ConvexHullTrick{ long[] A; long[] B; //C[i]はi番目の点に適用するのがi+1番目の点に適用するよりも大きくなる最大のx 単調増加になる long[] C; int p; int find; public ConvexHullTrick(int N){ A = new long[N]; B = new long[N]; C = new long[N]; p = 0; find = 0; } //aは単調増加でないといけない public void Add(long a,long b){ if(p == 0){ A[0] = a; B[0] = b;; p++; } else{ for(int i=p;i>0;i--){ long X = Compare(A[i-1],B[i-1],a,b); if(i == 1 || X > C[i-2]){ C[i-1] = X; A[i] = a; B[i] = b; p = i+1; break; } } } } //1つはAddしていないといけない public long Query(long x){ return Calc(x,findMax(x)); } int findMax(long x){ find = Math.Min(find,p-1); while(find < p-1 && C[find] < x){ find++; } while(find > 0 && C[find-1] >= x){ find--; } return find; } long Calc(long x,int i){ return A[i]*x + B[i]; } //(a1,b1)に適用する方が(a2,b2)に適用するより大きくなる最大のx long Compare(long a1,long b1,long a2,long b2){ return (b1-b2-1)/(a2-a1) - ((b1-b2-1)%(a2-a1) < 0 ? 1 : 0); } }
Submission Info
Submission Time | |
---|---|
Task | F - Contest with Drinks Hard |
User | leign |
Language | C# (Mono 4.6.2.0) |
Score | 0 |
Code Size | 3014 Byte |
Status | TLE |
Exec Time | 2105 ms |
Memory | 45116 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 1400 | ||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt |
All | sample_01.txt, sample_02.txt, subtask_1_high_equaly_01.txt, subtask_1_high_equaly_02.txt, subtask_1_high_equaly_03.txt, subtask_1_high_equaly_04.txt, subtask_1_high_rand_01.txt, subtask_1_high_rand_02.txt, subtask_1_high_rand_03.txt, subtask_1_high_rand_04.txt, subtask_1_killer_01.txt, subtask_1_killer_02.txt, subtask_1_low_equaly_01.txt, subtask_1_low_equaly_02.txt, subtask_1_low_equaly_03.txt, subtask_1_low_equaly_04.txt, subtask_1_low_rand_01.txt, subtask_1_low_rand_02.txt, subtask_1_low_rand_03.txt, subtask_1_low_rand_04.txt, subtask_1_max_high_equaly_01.txt, subtask_1_max_high_equaly_02.txt, subtask_1_max_high_equaly_03.txt, subtask_1_max_high_equaly_04.txt, subtask_1_max_high_rand_01.txt, subtask_1_max_high_rand_02.txt, subtask_1_max_high_rand_03.txt, subtask_1_max_high_rand_04.txt, subtask_1_max_low_equaly_01.txt, subtask_1_max_low_equaly_02.txt, subtask_1_max_low_equaly_03.txt, subtask_1_max_low_equaly_04.txt, subtask_1_max_low_rand_01.txt, subtask_1_max_low_rand_02.txt, subtask_1_max_low_rand_03.txt, subtask_1_max_low_rand_04.txt, subtask_1_max_rand_equaly_01.txt, subtask_1_max_rand_equaly_02.txt, subtask_1_max_rand_equaly_03.txt, subtask_1_max_rand_equaly_04.txt, subtask_1_max_rand_rand_01.txt, subtask_1_max_rand_rand_02.txt, subtask_1_max_rand_rand_03.txt, subtask_1_max_rand_rand_04.txt, subtask_1_min_rand_rand_01.txt, subtask_1_min_rand_rand_02.txt, subtask_1_rand_equaly_01.txt, subtask_1_rand_equaly_02.txt, subtask_1_rand_equaly_03.txt, subtask_1_rand_equaly_04.txt, subtask_1_rand_rand_01.txt, subtask_1_rand_rand_02.txt, subtask_1_rand_rand_03.txt, subtask_1_rand_rand_04.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 21 ms | 11092 KB |
sample_02.txt | AC | 21 ms | 11092 KB |
subtask_1_high_equaly_01.txt | TLE | 2104 ms | 27612 KB |
subtask_1_high_equaly_02.txt | TLE | 2104 ms | 27224 KB |
subtask_1_high_equaly_03.txt | TLE | 2104 ms | 15324 KB |
subtask_1_high_equaly_04.txt | TLE | 2104 ms | 32296 KB |
subtask_1_high_rand_01.txt | TLE | 2104 ms | 33748 KB |
subtask_1_high_rand_02.txt | TLE | 2104 ms | 37364 KB |
subtask_1_high_rand_03.txt | TLE | 2104 ms | 38984 KB |
subtask_1_high_rand_04.txt | TLE | 2104 ms | 28700 KB |
subtask_1_killer_01.txt | AC | 21 ms | 9172 KB |
subtask_1_killer_02.txt | AC | 21 ms | 11092 KB |
subtask_1_low_equaly_01.txt | TLE | 2104 ms | 31464 KB |
subtask_1_low_equaly_02.txt | TLE | 2104 ms | 31384 KB |
subtask_1_low_equaly_03.txt | TLE | 2104 ms | 31012 KB |
subtask_1_low_equaly_04.txt | TLE | 2104 ms | 38544 KB |
subtask_1_low_rand_01.txt | TLE | 2104 ms | 37852 KB |
subtask_1_low_rand_02.txt | TLE | 2104 ms | 22940 KB |
subtask_1_low_rand_03.txt | TLE | 2104 ms | 35304 KB |
subtask_1_low_rand_04.txt | TLE | 2104 ms | 30452 KB |
subtask_1_max_high_equaly_01.txt | TLE | 2104 ms | 42944 KB |
subtask_1_max_high_equaly_02.txt | TLE | 2104 ms | 37684 KB |
subtask_1_max_high_equaly_03.txt | TLE | 2104 ms | 39716 KB |
subtask_1_max_high_equaly_04.txt | TLE | 2104 ms | 43848 KB |
subtask_1_max_high_rand_01.txt | TLE | 2104 ms | 39700 KB |
subtask_1_max_high_rand_02.txt | TLE | 2104 ms | 43664 KB |
subtask_1_max_high_rand_03.txt | TLE | 2104 ms | 39720 KB |
subtask_1_max_high_rand_04.txt | TLE | 2104 ms | 41800 KB |
subtask_1_max_low_equaly_01.txt | TLE | 2104 ms | 35584 KB |
subtask_1_max_low_equaly_02.txt | TLE | 2104 ms | 39408 KB |
subtask_1_max_low_equaly_03.txt | TLE | 2104 ms | 41852 KB |
subtask_1_max_low_equaly_04.txt | TLE | 2104 ms | 35580 KB |
subtask_1_max_low_rand_01.txt | TLE | 2104 ms | 44124 KB |
subtask_1_max_low_rand_02.txt | TLE | 2104 ms | 45116 KB |
subtask_1_max_low_rand_03.txt | TLE | 2104 ms | 33552 KB |
subtask_1_max_low_rand_04.txt | TLE | 2105 ms | 42328 KB |
subtask_1_max_rand_equaly_01.txt | TLE | 2104 ms | 41788 KB |
subtask_1_max_rand_equaly_02.txt | TLE | 2104 ms | 37708 KB |
subtask_1_max_rand_equaly_03.txt | TLE | 2104 ms | 39348 KB |
subtask_1_max_rand_equaly_04.txt | TLE | 2104 ms | 37704 KB |
subtask_1_max_rand_rand_01.txt | TLE | 2104 ms | 39760 KB |
subtask_1_max_rand_rand_02.txt | TLE | 2104 ms | 39756 KB |
subtask_1_max_rand_rand_03.txt | TLE | 2104 ms | 40892 KB |
subtask_1_max_rand_rand_04.txt | TLE | 2104 ms | 43852 KB |
subtask_1_min_rand_rand_01.txt | AC | 21 ms | 11092 KB |
subtask_1_min_rand_rand_02.txt | AC | 21 ms | 11092 KB |
subtask_1_rand_equaly_01.txt | TLE | 2104 ms | 25880 KB |
subtask_1_rand_equaly_02.txt | TLE | 2104 ms | 31772 KB |
subtask_1_rand_equaly_03.txt | TLE | 2104 ms | 31960 KB |
subtask_1_rand_equaly_04.txt | TLE | 2104 ms | 31396 KB |
subtask_1_rand_rand_01.txt | TLE | 2105 ms | 38196 KB |
subtask_1_rand_rand_02.txt | TLE | 2104 ms | 41288 KB |
subtask_1_rand_rand_03.txt | TLE | 2104 ms | 36504 KB |
subtask_1_rand_rand_04.txt | TLE | 2104 ms | 30720 KB |