oj.uz

Submission #882385

# Submission time Handle Problem Language Result Execution time Memory
882385 2023-12-03T06:11:55 Z Requiem Potatoes and fertilizers (LMIO19_bulves) C++17
100 / 100
 124 ms 24868 KB 
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define INF 1e18
#define fi first
#define se second
#define endl "\n"
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define pi 3.14159265359
#define TASKNAME "bulves"
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; } 
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; } 
using namespace std; 
typedef pair<int,int> ii; 
typedef pair<int,ii> iii; 
typedef vector<int> vi; 
const int MAXN = 5e5 + 9;
int n;
int a[MAXN],b[MAXN],A,B;
namespace sub1 {
    void solve(){
       int ans = 0, bring = 0;
       for(int i=1;i<=n;i++){
           ans += abs(bring);
           if (a[i] == b[i]) continue;
           if (a[i] < b[i]) bring -= b[i] - a[i];
           else bring += a[i] - b[i];
       }
    }
}
namespace sub5{
    int dif[MAXN];
    void solve(){
        priority_queue<int> pq;
        int ans = 0;
        int d = 0;
        for(int i=1;i<=n;i++){
            dif[i] = dif[i-1] + a[i] - b[i];
            // cout<<dif[i]<<' ';
        }
        // cout<<endl;
        if (dif[1] < 0) ans -= dif[1], dif[1] = 0;
        if (dif[1] > dif[n]) ans += dif[1] - dif[n], dif[1] = dif[n];  
        pq.push(dif[1]);      
        for(int i=2;i<n;i++){
            if (dif[i] < 0) ans -= dif[i], dif[i] = 0;
            if (dif[i] > dif[n]) ans += dif[i] - dif[n], dif[i] = dif[n];
            if (dif[i] > pq.top()){
                pq.push(dif[i]);
            }
            else{
                pq.push(dif[i]);
                pq.push(dif[i]);
                ans += pq.top() - dif[i];
                pq.pop();
            }
        }
        
        cout<<ans<<endl;
    }
}
main() 
{ 
    fast; 
   if (fopen(TASKNAME".inp","r")){
        freopen(TASKNAME".inp","r",stdin); 
        freopen(TASKNAME".out","w",stdout); 
   }
   cin>>n;
   for(int i=1;i<=n;i++){
       cin>>a[i]>>b[i];
       A += a[i];
       B += b[i];
   } 
   assert(A >= B);
   sub5::solve();
}

Compilation message

bulves.cpp: In function 'void sub5::solve()':
bulves.cpp:40:13: warning: unused variable 'd' [-Wunused-variable]
   40 |         int d = 0;
      |             ^
bulves.cpp: At global scope:
bulves.cpp:66:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   66 | main()
      | ^~~~
bulves.cpp: In function 'int main()':
bulves.cpp:70:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
bulves.cpp:71:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4564 KB Output is correct
4 Correct 7 ms 9696 KB Output is correct
5 Correct 14 ms 12488 KB Output is correct
6 Correct 42 ms 15312 KB Output is correct
7 Correct 84 ms 20744 KB Output is correct
8 Correct 80 ms 20124 KB Output is correct
9 Correct 74 ms 20256 KB Output is correct
10 Correct 65 ms 18852 KB Output is correct
11 Correct 59 ms 18956 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4564 KB Output is correct
4 Correct 7 ms 9696 KB Output is correct
5 Correct 14 ms 12488 KB Output is correct
6 Correct 42 ms 15312 KB Output is correct
7 Correct 84 ms 20744 KB Output is correct
8 Correct 80 ms 20124 KB Output is correct
9 Correct 74 ms 20256 KB Output is correct
10 Correct 65 ms 18852 KB Output is correct
11 Correct 59 ms 18956 KB Output is correct
12 Correct 24 ms 13264 KB Output is correct
13 Correct 55 ms 19144 KB Output is correct
14 Correct 85 ms 22988 KB Output is correct
15 Correct 74 ms 22984 KB Output is correct
16 Correct 72 ms 22456 KB Output is correct
17 Correct 67 ms 19260 KB Output is correct
18 Correct 1 ms 4440 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4440 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 2 ms 4952 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4564 KB Output is correct
4 Correct 1 ms 4440 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 2 ms 4952 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4440 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4528 KB Output is correct
14 Correct 1 ms 4440 KB Output is correct
15 Correct 2 ms 4576 KB Output is correct
16 Correct 1 ms 4440 KB Output is correct
17 Correct 1 ms 4440 KB Output is correct
18 Correct 1 ms 4444 KB Output is correct

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4564 KB Output is correct
4 Correct 1 ms 4440 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 2 ms 4952 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 7 ms 9696 KB Output is correct
12 Correct 14 ms 12488 KB Output is correct
13 Correct 42 ms 15312 KB Output is correct
14 Correct 84 ms 20744 KB Output is correct
15 Correct 80 ms 20124 KB Output is correct
16 Correct 74 ms 20256 KB Output is correct
17 Correct 65 ms 18852 KB Output is correct
18 Correct 59 ms 18956 KB Output is correct
19 Correct 24 ms 13264 KB Output is correct
20 Correct 55 ms 19144 KB Output is correct
21 Correct 85 ms 22988 KB Output is correct
22 Correct 74 ms 22984 KB Output is correct
23 Correct 72 ms 22456 KB Output is correct
24 Correct 67 ms 19260 KB Output is correct
25 Correct 1 ms 4444 KB Output is correct
26 Correct 1 ms 4528 KB Output is correct
27 Correct 1 ms 4440 KB Output is correct
28 Correct 2 ms 4576 KB Output is correct
29 Correct 1 ms 4440 KB Output is correct
30 Correct 1 ms 4440 KB Output is correct
31 Correct 1 ms 4444 KB Output is correct
32 Correct 1 ms 4440 KB Output is correct
33 Correct 27 ms 13560 KB Output is correct
34 Correct 72 ms 19480 KB Output is correct
35 Correct 115 ms 24780 KB Output is correct
36 Correct 103 ms 20680 KB Output is correct
37 Correct 79 ms 22852 KB Output is correct
38 Correct 124 ms 24868 KB Output is correct
39 Correct 69 ms 20412 KB Output is correct
40 Correct 71 ms 20368 KB Output is correct
41 Correct 64 ms 19776 KB Output is correct
42 Correct 64 ms 19256 KB Output is correct
43 Correct 69 ms 20168 KB Output is correct
44 Correct 76 ms 19148 KB Output is correct
45 Correct 102 ms 23344 KB Output is correct
46 Correct 86 ms 19292 KB Output is correct
47 Correct 69 ms 19004 KB Output is correct