oj.uz

Submission #91125

# Submission time Handle Problem Language Result Execution time Memory
91125 2018-12-26T10:26:44 Z Aydarov03 Divide and conquer (IZhO14_divide) C++14
48 / 100
 1000 ms 4152 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
int x[N] , g[N] , e[N];
int n;
int maxg;
int l , r;

inline bool check( int mid )
{
    int gold;
    int lenergy;
    int genergy;

    for(int i = 1; i <= n; i++)
    {
        gold = 0;
        lenergy = 0;
        genergy = 0;
        for(int j = i; j <= n; j++)
        {
            gold += g[j];
            lenergy = x[j] - x[i];
            genergy += e[j];
            if( genergy >= lenergy && gold >= mid )return true;
        }
    }
    return false;

}




main()
{
    scanf("%lld" , &n);

    for(int i = 1; i <= n; i++)
    {
        scanf("%lld %lld %lld" , &x[i] , &g[i] , &e[i]);
        maxg += g[i];
    }

    r = maxg + 1;

    while( r - l > 1 )
    {
        int mid = (l + r) / 2LL;

        if( check(mid) )l = mid;
        else    r = mid;
    }

    printf("%lld" , l);

}

Compilation message

divide.cpp:36:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
divide.cpp: In function 'int main()':
divide.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld" , &n);
     ~~~~~^~~~~~~~~~~~~
divide.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld %lld" , &x[i] , &g[i] , &e[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 676 KB Output is correct
2 Correct 2 ms 676 KB Output is correct
3 Correct 3 ms 676 KB Output is correct
4 Correct 6 ms 676 KB Output is correct
5 Correct 13 ms 676 KB Output is correct
6 Correct 3 ms 676 KB Output is correct
7 Correct 2 ms 676 KB Output is correct
8 Correct 2 ms 676 KB Output is correct
9 Correct 19 ms 676 KB Output is correct
10 Correct 66 ms 676 KB Output is correct
11 Correct 606 ms 936 KB Output is correct
12 Correct 604 ms 1084 KB Output is correct

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1084 KB Output is correct
2 Correct 4 ms 1084 KB Output is correct
3 Correct 5 ms 1084 KB Output is correct
4 Correct 19 ms 2976 KB Output is correct
5 Correct 25 ms 2984 KB Output is correct
6 Correct 48 ms 4152 KB Output is correct
7 Correct 35 ms 4152 KB Output is correct
8 Correct 35 ms 4152 KB Output is correct
9 Correct 34 ms 4152 KB Output is correct
10 Execution timed out 1085 ms 4152 KB Time limit exceeded
11 Halted 0 ms 0 KB -