제출 #1264793

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1264793		Nika533	Trains (BOI24_trains)	C++20	100 / 100	196 ms	8524 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define MOD 1000000007
using namespace std;

const int N=1e5+5,SQ=405;
int n,d[N],x[N],dp[N],num[SQ][SQ];
vector<pair<pii,int>> g[N];

main() {
    cin>>n; int sq=400;
    for (int i=1; i<=n; i++) cin>>d[i]>>x[i];
    dp[1]=1;
    int ans=0;
    for (int i=1; i<=n; i++) {
        for (int o=1; o<=sq; o++) {
            dp[i]+=num[o][i%o]; dp[i]%=MOD;
        }
        if (d[i]>=sq) {
            for (int j=i+d[i]; j<=min(n,i+d[i]*x[i]); j+=d[i]) {
                dp[j]+=dp[i]; dp[j]%=MOD;
            }
        }
        else if (d[i]>=1) {
            int r=i+d[i]*x[i];
            num[d[i]][i%d[i]]+=dp[i];
            if (r<=n) g[r].pb({{d[i],i%d[i]},dp[i]});
        }
        ans+=dp[i]; ans%=MOD;
        for (auto AA:g[i]) {
            num[AA.f.f][AA.f.s]-=AA.s;
        }
        // cout<<i<<" "<<dp[i]<<endl;
    }
    cout<<ans<<endl;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp:15:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   15 | main() {
      | ^~~~

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