Submission #1308415

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308415		thnhann	Mizuyokan 2 (JOI23_mizuyokan2)	C++20	0 / 100	164 ms	2004 KiB

mizuyokan2

//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx,avx2,fma,lzcnt,popcnt")
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define ill pair<ll,ll>
#define el cout<<'\n'
#define int long long

const ll mod=1e9+7;
const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
const int nmax=5e5;
const int inf =2e9;

void add(int &a, int b) {
    a += b;
    if (a >= mod) a -= mod;
    if (a < 0) a += mod;
}

template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

using namespace std;

mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r)
{
    return uniform_int_distribution<int>(l, r) (rd);
}

int n;
int d[nmax + 5];
int q;

int len[nmax + 5];
int dp[nmax + 5];
int pre[nmax + 5];

signed main()
{
   ios::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);

   cin >> n;
   for(int i=1;i<=n;i++)
   {
        cin >> d[i];
   }
   cin >> q;
   while(q--)
   {
       int x,y,l,r;
       cin >> x >> y >> l >> r;
       d[x] = y;

       int m = 0;
       for(int i=l + 1;i <= r;i++)
        len[++m] = d[i];

       pre[0] = 0;
       for(int i=1;i<=m;i++)
            pre[i] = pre[i - 1] + len[i];

       dp[1] = 1;
       dp[0] = 0;
       for(int i=2;i<=m;i++)
       {
           dp[i] = 1;
           for(int j=1;j<i;j++)
           {
               int sum = pre[i - 1] - pre[j - 1];
               if(sum > len[j - 1] && sum > len[i])
                chkmax(dp[i],dp[j - 1] + 2);
           }
       }
       cout << dp[m];el;

   }


}
//  "Can i get a kiss? And can u make it last forever?"

• Subtask 1: 0 / 6
• Subtask 2: 0 / 9
• Subtask 3: 0 / 13
• Subtask 4: 0 / 32
• Subtask 5: 0 / 29
• Subtask 6: 0 / 11