oj.uz

Submission #102970

# Submission time Handle Problem Language Result Execution time Memory
102970 2019-03-28T09:23:45 Z brcode Divide and conquer (IZhO14_divide) C++14
17 / 100
 144 ms 5728 KB 
#include <iostream>

using namespace std;
const long long MAXN = 1e5+5;
long long pos[MAXN];
long long d[MAXN];
long long g[MAXN];
int main(){
    long long n;
    cin>>n;
    for(long long i=1;i<=n;i++){
        cin>>pos[i]>>g[i]>>d[i];
    }
    long long l = 1;
    long long r = 1;
    long long ans = g[1];
    long long holdlen = d[1];
    long long holdgold = g[1];
    
    while(l<=r && (r<=n)){
       // cout<<holdgold<<" "<<holdlen<<" "<<l<<" "<<r<<endl;
        if(l == r){
            ans = max(ans,g[r]);
            r++;
            holdlen+=d[r];
            holdgold+=g[r];
            continue;
        }
        if(pos[r]-pos[l]>holdlen){
            
            holdlen-=d[l];
            holdgold-=g[l];
            l++;
            
            continue;
        }else{
            ans = max(ans,holdgold);
            r++;
            holdlen+=d[r];
            holdgold+=g[r];
        }
    }
    ans = max(ans,holdgold);
    cout<<ans<<endl;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Incorrect 2 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 512 KB Output is correct
2 Correct 16 ms 632 KB Output is correct
3 Correct 14 ms 768 KB Output is correct
4 Correct 81 ms 2608 KB Output is correct
5 Correct 63 ms 2936 KB Output is correct
6 Correct 144 ms 5728 KB Output is correct
7 Correct 99 ms 4548 KB Output is correct
8 Correct 92 ms 4640 KB Output is correct
9 Correct 92 ms 4472 KB Output is correct
10 Incorrect 111 ms 4396 KB Output isn't correct
11 Halted 0 ms 0 KB -