oj.uz

Submission #874301

# Submission time Handle Problem Language Result Execution time Memory
874301 2023-11-16T16:11:54 Z ngjabach Sjeckanje (COCI21_sjeckanje) C++14
15 / 110
 38 ms 2908 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=2;i<=n;++i) d[i]=a[i]-a[i-1];
            dp[1][0]=-INF; dp[1][1]=-INF;
            for(int i=2;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-1]*d[i]>=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][0],dp[n][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 17 ms 2616 KB Output is correct
2 Correct 18 ms 2620 KB Output is correct
3 Correct 18 ms 2392 KB Output is correct
4 Correct 18 ms 2616 KB Output is correct
5 Correct 20 ms 2624 KB Output is correct
6 Correct 17 ms 2396 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2616 KB Output is correct
2 Correct 18 ms 2620 KB Output is correct
3 Correct 18 ms 2392 KB Output is correct
4 Correct 18 ms 2616 KB Output is correct
5 Correct 20 ms 2624 KB Output is correct
6 Correct 17 ms 2396 KB Output is correct
7 Incorrect 38 ms 2908 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2616 KB Output is correct
2 Correct 18 ms 2620 KB Output is correct
3 Correct 18 ms 2392 KB Output is correct
4 Correct 18 ms 2616 KB Output is correct
5 Correct 20 ms 2624 KB Output is correct
6 Correct 17 ms 2396 KB Output is correct
7 Incorrect 38 ms 2908 KB Output isn't correct
8 Halted 0 ms 0 KB -