Submission #1043251

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043251		guagua0407	Trains (BOI24_trains)	C++17	100 / 100	144 ms	8424 KiB

Main

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

const int mod=1e9+7;
const int B=350;

int main() {_
    int n;
    cin>>n;
    vector<ll> d(n),x(n);
    for(int i=0;i<n;i++){
        cin>>d[i]>>x[i];
    }
    vector<ll> dp(n);
    vector<vector<ll>> sum(B,vector<ll>(B));
    vector<vector<int>> en(n);
    dp[0]=1;
    for(int i=0;i<n;i++){
        for(int j=1;j<B;j++){
            dp[i]=(dp[i]+sum[j][i%j])%mod;
        }
        if(d[i]>=B){
            for(int j=1;j<=x[i] and i+j*d[i]<n;j++){
                dp[i+j*d[i]]=(dp[i+j*d[i]]+dp[i])%mod;
            }
        }
        else if(d[i]>0){
            sum[d[i]][i%d[i]]=(sum[d[i]][i%d[i]]+dp[i])%mod;
            if(i+x[i]*d[i]<n) en[i+x[i]*d[i]].push_back(i);
        }
        for(auto j:en[i]){
            sum[d[j]][j%d[j]]=(sum[d[j]][j%d[j]]-dp[j])%mod;
            if(sum[d[j]][j%d[j]]<0) sum[d[j]][j%d[j]]+=mod;
        }
    }
    ll ans=0;
    for(int i=0;i<n;i++){
        ans=(ans+dp[i])%mod;
    }
    cout<<ans<<'\n';
    return 0;
}
//maybe its multiset not set
//yeeorz
//laborz

Compilation message (stderr)

Main.cpp: In function 'void setIO(std::string)':
Main.cpp:15:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:16:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 13 / 13
• Subtask 3: 16 / 16
• Subtask 4: 34 / 34
• Subtask 5: 29 / 29