Submission #1105947

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105947		Bananabread	Harvest (JOI20_harvest)	C++17	5 / 100	1640 ms	337124 KiB

harvest

#include<bits/stdc++.h>
#define ll long long
#define ntr "\n"
#define mod (ll)(1e9+7)
#define taskname ""
#define frep freopen(taskname".inp","r",stdin); freopen(taskname".out","w",stdout);
using namespace std;
ll a[5001],b[5001];
ll n,m,l,c,q;
vector<pair<ll,ll>> adj[7001];
ll loop1[7001][3001];
ll loop2[7001][3001];
ll vis[7001];
ll par;
void dfs(ll u,ll dist){
    if(vis[u]>=2) return ;
    vis[u]++;
    if(vis[u]==1) loop1[u][par]=dist;
    else loop2[u][par]=dist;
    for(auto [v,w]:adj[u]){
        dfs(v,dist+w);
    }
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    //frep;
    cin>>n>>m>>l>>c;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++) cin>>b[i];
    for(int i=1;i<=n;i++){
        ll mn=1e18,pos;
        for(int j=1;j<=n;j++){
            //if(i==j) continue;
            ll v=((a[i]-a[j])%l+l)%l;
            ll cost=(c-v+l-1)/l*l+v;
            if(cost<mn){
                mn=cost,pos=j;
            }
        }
//        cout<<i<<' '<<pos<<' '<<mn<<ntr;
        adj[i].push_back({pos,mn});
    }
    for(int i=1;i<=m;i++){
        ll v=upper_bound(a+1,a+n+1,b[i])-a-1;
        if(v==0) v=n;
        ll cost=((b[i]-a[v])%l+l)%l;
        adj[i+n].push_back({v,cost});
//        cout<<i<<' '<<v<<' '<<cost<<ntr;
    }
    memset(loop1,0x3f,sizeof(loop1));
    memset(loop2,0x3f,sizeof(loop2));
    for(int i=1;i<=m;i++){
        par=i;
        dfs(i+n,0);
        for(int j=1;j<=n+m;j++) vis[j]=0;
    }
//    for(int i=1;i<=n;i++){
//        for(int j=1;j<=m;j++){
//            cout<<loop1[i][j]<<' ';
//        }
//        cout<<ntr;
//    }
    cin>>q;
    for(int i=1;i<=q;i++){
        ll u,t;
        cin>>u>>t;
        ll ans=0;
        for(int j=1;j<=m;j++){
            if(loop1[u][j]>t) continue;
            ans++;
            ll diff=loop2[u][j]-loop1[u][j];
            //cout<<diff<<' ';
            ans+=(t-loop1[u][j])/diff;
        }
        cout<<ans<<ntr;
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 20
• Subtask 3: 0 / 75