Submission #1270183

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270183		cr7	Trains (BOI24_trains)	C++17	100 / 100	230 ms	9244 KiB

Main

#include<bits/stdc++.h>
#define dn cout << "\n";
#define ll long long
#define F first
#define S second
#define name "tasksss"
#define con(x) __builtin_popcount(x)
#define pb push_back
#define bit(i, j) ((i >> j) & 1)

using namespace std;
const int N = 2e5 + 2;
const int BL = 325;
const ll MOD = 1e9 + 7;

int n;
pair<int,int> p[N];
ll dp[N], total[330][330];
vector<int> pos[N];
void add(ll &a, ll b){
    a += b;
    while(a >= MOD) a -= MOD;
}
void sub(ll &a, ll b){
    a -= b;
    while(a < 0) a += MOD;
}
ll dem = 0;
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(dem, 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 j : pos[i]){
            sub(total[p[j].F][j % p[j].F], dp[j]);
        }
    }
    cout << dem;

}

main(){
    if(fopen(name".inp","r")){
        freopen(name".inp","r",stdin);
        freopen(name".out","w",stdout);
    }
    solve();
}

Compilation message (stderr)

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