oj.uz

Submission #874313

# Submission time Handle Problem Language Result Execution time Memory
874313 2023-11-16T16:28:42 Z ngjabach Sjeckanje (COCI21_sjeckanje) C++14
55 / 110
 67 ms 17964 KB 
// NgJaBach: Forever Meadow <3

#include<bits/stdc++.h>

using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long int ll;
typedef unsigned long long ull;
#define pb push_back
#define pob pop_back
#define mp make_pair
#define upb upper_bound
#define lwb lower_bound
#define bend(a) a.begin(),a.end()
#define rev(x) reverse(bend(x))
#define mset(a) memset(a, 0, sizeof(a))
#define fi first
#define se second
#define gcd __gcd
#define getl(s) getline(cin, s);
#define setpre(x) fixed << setprecision(x)
#define endl '\n'
const int N=200050,M=1000000007;
const ll INF=1e18+7;
struct ask{
    int x,y;
    ll z;
};
ll arr[N];
int q,n;
vector<ask>queries;
namespace sub1{
    ll a[205],dp[205],minis[205][205],maxis[205][205];
    vector<ll>ans;
    vector<ll>solve(){
        ans.clear();
        int x,y; ll z;
        for(int i=1;i<=n;++i) a[i]=arr[i];
        for(int t=0;t<q;++t){
            x=queries[t].x; y=queries[t].y; z=queries[t].z;
            for(int i=x;i<=y;++i) a[i]+=z;
            for(int i=1;i<=n;++i){
                maxis[i][i]=a[i];
                minis[i][i]=a[i];
                for(int j=i+1;j<=n;++j){
                    maxis[i][j]=max(maxis[i][j-1],a[j]);
                    minis[i][j]=min(minis[i][j-1],a[j]);
                }
            }
            dp[0]=0;
            for(int i=1;i<=n;++i){
                dp[i]=-INF;
                for(int j=1;j<=i;++j) dp[i]=max(dp[i],dp[j-1]+maxis[j][i]-minis[j][i]);
            }
            ans.pb(dp[n]);
        }
        return ans;
    }
}
namespace sub2{
    ll a[3005],dp[3005][2],d[3005];
    vector<ll>ans;
    vector<ll>solve(){
        ans.clear();
        int x,y; ll z;
        for(int i=1;i<=n;++i) a[i]=arr[i];
        for(int t=0;t<q;++t){
            x=queries[t].x; y=queries[t].y; z=queries[t].z;
            for(int i=x;i<=y;++i) a[i]+=z;
            for(int i=1;i<n;++i) d[i]=a[i]-a[i+1];
            dp[0][0]=0; dp[0][1]=0; d[n]=0;
            for(int i=1;i<n;++i){
                dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
                dp[i][1]=max(dp[i-1][0],dp[i-1][1]*(d[i]*d[i-1]>=0))+abs(d[i]);
            }
//            cout<<"a: "; for(int i=1;i<=n;++i) cout<<a[i]<<" "; cout<<endl;
//            cout<<"d: "; for(int i=1;i<=n;++i) cout<<d[i]<<" "; cout<<endl;
//            cout<<"dp"<<endl;
//            for(int j=0;j<2;++j) for(int i=1;i<=n;++i) cout<<dp[i][j]<<" "; cout<<endl;
            ans.pb(max(dp[n-1][0],dp[n-1][1]));
        }
        return ans;
    }
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
//    freopen("RECIPE.inp","r",stdin);
//    freopen("RECIPE.out","w",stdout);
    cin>>n>>q;
    for(int i=1;i<=n;++i) cin>>arr[i];
    for(int i=0;i<q;++i){
        int x,y,z;
        cin>>x>>y>>z;
        queries.pb({x,y,z});
    }
    vector<ll>ans;
//    if(n<=200 and q<=200) ans=sub1::solve();
//    else if(n<=3000 and q<=3000) 
    ans=sub2::solve();
    for(ll &tmp:ans) cout<<tmp<<endl;
    return 0;
}
/*
==================================+
INPUT:                            |
------------------------------    |

------------------------------    |
==================================+
OUTPUT:                           |
------------------------------    |

------------------------------    |
==================================+
*/

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 37 ms 2896 KB Output is correct
8 Correct 35 ms 2652 KB Output is correct
9 Correct 35 ms 2808 KB Output is correct
10 Correct 35 ms 2652 KB Output is correct
11 Correct 35 ms 2648 KB Output is correct
12 Correct 36 ms 2868 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 37 ms 2896 KB Output is correct
8 Correct 35 ms 2652 KB Output is correct
9 Correct 35 ms 2808 KB Output is correct
10 Correct 35 ms 2652 KB Output is correct
11 Correct 35 ms 2648 KB Output is correct
12 Correct 36 ms 2868 KB Output is correct
13 Runtime error 67 ms 17964 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -