oj.uz

Submission #870143

# Submission time Handle Problem Language Result Execution time Memory
870143 2023-11-07T03:51:19 Z nghia0912 Sjeckanje (COCI21_sjeckanje) C++17
55 / 110
 41 ms 3672 KB 
#define COPYRIGHT CODE BY TRINH TUAN NGHIA
#include<bits/stdc++.h>
#define Boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ll long long
#define endl "\n"
#define st first
#define nd second
#define ii pair <ll,ll>
#define iii pair <ll,ii>
#define iiii pair <ii,ii>
#define pb push_back
#define NAME "recipe"
#define int long long
using namespace std;
const int N = 2e5 + 10;
const int Nsub1 = 210;
const int Nsub2 = 3e3 + 10;
int n,q ;
long long  dp[3010];
ll a[N];

void inp (){
    cin >> n >> q;
    for (int i = 1;i <= n; ++i){
        cin >> a[i];
    }
}
void reset(){
    for (int i =1 ; i <= n; ++i)dp[i] = 0;
}
void sub1(){
    while (q--){
        reset();
        int l, r, x;
        cin >> l >> r >> x;
        for (int i = l; i <= r; ++i){
            a[i] += x;
        }
        for (int i = 1; i <= n; ++i){
            ll minn = a[i];
            ll maxx = a[i];
            for (int j = i; j >= 1; --j){
                minn = min(minn, a[j]);
                maxx = max(maxx, a[j]);
                dp[i] = max({dp[i], dp[j - 1] + a[i] - minn, dp[j - 1] + maxx - a[i]});
//                if (i == 2 and j == 1)cout << minn << " " << maxx << "\n";
            }
//            cout << a[i] << " ";
        }
//        cout << "\n";
//        for (int i =1 ; i <= n; ++i)cout << dp[i] << " ";
//        cout << "\n";
        cout << dp[n] << "\n";
    }

}
void sub2(){
    while (q--){
        reset();
        int l, r, x;
        cin >> l >> r >> x;
        for (int i = l; i <= r; ++i){
            a[i] += x;
        }
        ll minn = 1e18;
        ll maxx = 0;
        ll minndp = 1e18;
        ll maxxdp =-1e18;
        for (int i = 1; i <= n; ++i){
            dp[i] = max({dp[i -1 ], a[i] - minndp, maxxdp - a[i]});
            minndp = min(minndp, a[i] - dp[i - 1]);
            maxxdp = max(maxxdp, dp[i - 1] + a[i]);
//            cout << dp[i] << " ";
            //cout << i << " " << dp[i] << " " << minndp << " " << maxxdp << endl;
        }
//        cout << endl;
        cout << dp[n] << endl;
    }
}
void solve(){
//    sub1();
        sub2();
}
signed main (){
    if (fopen(NAME".inp", "r")){
        freopen(NAME".inp", "r", stdin);
        freopen(NAME".out", "w", stdout);
    }
    Boost;
    inp();
    solve();
}
/*
input

*/

/*
output

*/

Compilation message

Main.cpp: In function 'void sub2()':
Main.cpp:65:12: warning: unused variable 'minn' [-Wunused-variable]
   65 |         ll minn = 1e18;
      |            ^~~~
Main.cpp:66:12: warning: unused variable 'maxx' [-Wunused-variable]
   66 |         ll maxx = 0;
      |            ^~~~
Main.cpp: In function 'int main()':
Main.cpp:86:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         freopen(NAME".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:87:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |         freopen(NAME".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 41 ms 604 KB Output is correct
8 Correct 39 ms 348 KB Output is correct
9 Correct 39 ms 348 KB Output is correct
10 Correct 39 ms 348 KB Output is correct
11 Correct 40 ms 516 KB Output is correct
12 Correct 39 ms 344 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 41 ms 604 KB Output is correct
8 Correct 39 ms 348 KB Output is correct
9 Correct 39 ms 348 KB Output is correct
10 Correct 39 ms 348 KB Output is correct
11 Correct 40 ms 516 KB Output is correct
12 Correct 39 ms 344 KB Output is correct
13 Runtime error 16 ms 3672 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -