Submission #812711

#	Time	Username	Problem	Language	Result	Execution time	Memory
812711		Cookie	Garden (JOI23_garden)	C++14	30 / 100	3078 ms	8424 KiB

garden

#include<bits/stdc++.h>
#include<fstream>
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
//ifstream fin("FEEDING.INP");
//ofstream fout("FEEDING.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const int base = 74;
const ll mod = 1e9 + 7, inf = 1e9, mxv = 1005, mxn = 5e5 + 5;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, m, d;
int a[mxn + 1], b[mxn + 1], x[mxn + 1], y[mxn + 1];
bool vis[5005];
vt<int>comp[5005];
signed main()
{
     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m >> d;
    for(int i = 1; i <= n; i++){
        cin >> a[i] >> b[i];
        vis[a[i]] = 1;
    }
    int ans = inf;
    for(int i = 1; i <= m; i++){
        cin >> x[i] >> y[i];
        comp[x[i]].pb(y[i]);
    }
    for(int i = 0; i < d; i++){
        vt<int>cor;
        int last = -1;
        for(int j = i; j < i + d; j++){
            if((j < d && vis[j]) || (j >= d && vis[j - d])){
                last = j; 
            }
        }
        assert(last != -1);
        for(int j = 1; j <= n; j++){
            cor.pb(b[j]);
        }
        for(int j = i + d - 1; j >= last; j--){
            sort(cor.begin(), cor.end());
            int mx = 0;
            if(sz(cor) > 1){
                for(int k = 1; k < sz(cor); k++){
                    mx = max(mx, cor[k] - cor[k - 1]);
                }
                mx = max(mx, (cor[0] - cor.back() + d) % d);
            }
            //for(auto k: cor)cout << k << ' ';
            //cout << ": " << mx << "\n";
            if(mx == 0){
                ans = min(ans, (j - i + 1));
            }else{
                ans = min(ans, (j - i + 1) * (d - mx + 1));
            }
            
            for(auto k: comp[j % d])cor.pb(k);
        }
    }
    cout << ans;
    return(0);
}

• Subtask 1: 0 / 15
• Subtask 2: 6 / 6
• Subtask 3: 8 / 8
• Subtask 4: 16 / 16
• Subtask 5: 0 / 30
• Subtask 6: 0 / 25