Submission #1266389

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266389		herominhsteve	Trains (BOI24_trains)	C++20	37 / 100	204 ms	257188 KiB

Main

#include <bits/stdc++.h>
#define el '\n'
#define FNAME "trains"
#define allof(x) x.begin(),x.end()
#define allof1(x) x.begin()+1,x.end()
#define mset(x,n) memset(x,(n),sizeof(x))
using namespace std;
const long long MOD = (long long) 1e9+7;
template<class X,class Y> bool minimize(X &a,Y b){ if (a>b) {a=b; return true;} return false;}
template<class X,class Y> bool maximize(X &a,Y b){ if (a<b) {a=b; return true;} return false;}

void setup(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
	if (fopen(FNAME".inp","r")){
		freopen(FNAME".inp","r",stdin);
		freopen(FNAME".out","w",stdout);
	}
}

struct Train{
	long long d,x;
	int ID;
	Train(): d(0),x(0),ID(-1){}
	Train(long long D,long long X,int _ID): d(D), x(X),ID(_ID){}
	bool canTravel(int cID){
		if (!d) return false;
		if (cID<=ID or ID==-1) return false;
		cID -= ID;
		if (cID % d) return false;
		return (cID/d <= x);
	}
};

int n;
vector<Train> a;

void init(){
	cin>>n;
	a.assign(n+1,Train());
	for (int i=1;i<=n;i++){
		cin>>a[i].d>>a[i].x;
		a[i].ID=i;
	}
}

inline void add(long long &x,long long y){
	x+=y;
	if (x>=MOD) x-=MOD;
}

namespace BruteDP{
	void solve(){
		// ! dp[i]: # of ways to get to city i and ending at city i from city 1
		vector<long long> dp(n+1,0);
		dp[1] = 1;
		for (int i=2;i<=n;i++){
			for (int j=i-1;j>=1;j--){
				if (a[j].canTravel(i)) add(dp[i],dp[j]);
			}
		}
		long long res = 0;
		for (int i=1;i<=n;i++) add(res,dp[i]);
		cout<<res;
		exit(0);
	}
};

namespace FinalDP{
	/*
	 ! jumpSum[jump][r]: sum accumulated with Jump jump, remainder r
	 * jump update is written in form i + t * x
	 ? i.e, destination of 2 (d=3) 2 + 1 * 3 = 5, 2 + 2*3= 8, 14, 17
	 ? Notice how all destination of 2 all have remainder 2 under modulo 3
	 ? also more 3,4...
	 * => i % jump = r returns correctly to its starting place
	*/
	vector<vector<long long>> jumpSum;
	// ! lazy[i][jump]
	// ? difference array to lazily update jumpSum
	vector<vector<long long>> lazy;
	int S;

	void range(int ID,int jump,long long delta){
		if (ID>n) return;
		if (delta < 0) delta+=MOD;
		add(lazy[ID][jump],delta);
	}

	void solve(){
		S = static_cast<int>(sqrt(n)) + 1;
		jumpSum.assign(S+1,vector<long long>(S+1,0));
		lazy.assign(n+1,vector<long long>(S+1,0));
		
		vector<long long> dp(n+1,0);
		dp[1] = 1;

		for (int i=1;i<=n;i++){
			for (int jump=1;jump<S;jump++){
				int r = i%jump;
				add(jumpSum[jump][r],lazy[i][jump]);
				add(dp[i],jumpSum[jump][r]);
			}

			if (!a[i].d) continue;

			if (a[i].d < S){
				int jump = a[i].d;
				range(i + jump,jump,+dp[i]);
				range(i + jump * (a[i].x+1),jump,-dp[i]);
			} else{
				int x = a[i].x;
				int jump = a[i].d;
				for (int j=i + jump,t=1; t<=x and j<=n; j+=jump)
					add(dp[j],dp[i]);
			}
		}
		long long res=0;
		for (int i=1;i<=n;i++) add(res,dp[i]);
		cout<<res;
		exit(0);
	}
};

void sol(){
	if (n<=1e4) BruteDP::solve();
	FinalDP::solve();
}

int main(){
    setup();
    init();
    sol();
}

Compilation message (stderr)

Main.cpp: In function 'void setup()':
Main.cpp:16:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |                 freopen(FNAME".inp","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:17:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |                 freopen(FNAME".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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