Submission #1266293

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266293		herominhsteve	Trains (BOI24_trains)	C++20	21 / 100	188 ms	2120 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);
	}
};

void sol(){
	if (n<=1e4) BruteDP::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: 0 / 16
• Subtask 4: 0 / 34
• Subtask 5: 0 / 29