Submission #1269853

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269853		cr7	Trains (BOI24_trains)	C++17	100 / 100	200 ms	6732 KiB

Main

#include<bits/stdc++.h>
#define ll long long
#define dn cout << "\n";
#define name "task"
#define F first
#define S second
#define B_1(x) __buildtin_popcount(x)
#define bit(i, j) ((i >> j) & 1)
#define pb push_back
using namespace std;
const int M = 1e5 + 2;
const ll MOD = 1e9 + 7;
const int BL = 320;
int n;
pair<int,int> p[M];
ll total[BL + 2][BL + 2];
ll dp[M], rs = 0;
vector<int> pos[M + 2];
void add(ll &a, ll b){
    a += b;
    while(a >= MOD) a -= MOD;
}
void mus(ll &a, ll b){
    a -= b;
    while(a < 0) a += MOD;
}
void solve(){
    cin >> n;
    for(int i = 1; i <= n; i ++){
        cin >> p[i].F >> p[i].S;
        if(p[i].F != 0){
            p[i].S = min(p[i].S, (n - i)/ p[i].F);
        }
        p[i].S = i + p[i].F * p[i].S;
    }
    dp[1] = 1;
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= BL; j ++)
            add(dp[i], total[j][i % j]);
        add(rs, dp[i]);
        if(p[i].F != 0){
            if(p[i].F >= BL){
                for(int j = i + p[i].F; j <= p[i].S; j += p[i].F)
                    add(dp[j], dp[i]);
            }
            else{
                add(total[p[i].F][i % p[i].F], dp[i]);
                pos[p[i].S].pb(i);

            }
        }
        for(int x : pos[i])
            mus(total[p[x].F][x % p[x].F], dp[x]);
    }
    cout << rs;
}
main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if(fopen(name".inp","r")){
        freopen(name".inp","r",stdin);
        freopen(name".out","w",stdout);
    }
    solve();
}

Compilation message (stderr)

Main.cpp:57:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   57 | main(){
      | ^~~~
Main.cpp: In function 'int main()':
Main.cpp:60:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         freopen(name".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:61:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         freopen(name".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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