Submission #994769

#	Time	Username	Problem	Language	Result	Execution time	Memory
994769		MisalignedDiv	Trains (BOI24_trains)	C++14	0 / 100	172 ms	251864 KiB

Main

#include <iostream>
#include <bits/stdc++.h>
#include <map>
#include <vector>
#include <cmath>
#include <algorithm>
#include <unistd.h>  
#include <cstdio>

using namespace std;

typedef long long ll;
typedef unsigned int uint;
typedef pair<ll, int> pil;
typedef vector<int> vi;
typedef long long ll;
typedef pair<ll,ll> pll;

const int SS = 1e5 + 8, MOD = 1e9 + 7,
          SQR = 319;
class Solution{
	public:
	ll N, di, xi,
	   DP[SS], seq[SS][SQR];
	vector<pll> arr = {{-1, -1}};
	ll profitProfit(){
		cin >> N;
		fill(DP, DP + SS, -1);
		memset(seq, 0, sizeof(seq));
		for (int i = 0; i < N; i++){
			cin >> di >> xi;
			arr.push_back( make_pair(di, xi) );
		}
		for (int curr = N; curr >= 1; curr--){
			auto [diff, x] = arr[curr];
			DP[curr] = 1;
			if (diff >= SQR){
				for (int child = diff + curr, t = 0; child <= N && t < x; child += diff, t++){
					DP[curr] += DP[child];
				}
				DP[curr] %= MOD;
			}
			else if (diff != 0){
				if (diff + curr < N)            DP[curr] += seq[curr + diff][diff];
				if (diff + curr * (x + 1) < N)  DP[curr] -= seq[curr + diff * (x + 1)][diff];
				DP[curr] = (DP[curr] % MOD + MOD) % MOD;
			}
			if (curr == N) seq[curr][1] = DP[curr];
			for (int d = 1; d < SQR; d++){
				if (d + curr > N) continue;
				seq[curr][d] = (seq[curr + d][d] + DP[curr]) % MOD;
			}
		}
		return DP[1];
	}	
};


int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	Solution p;
	cout << p.profitProfit();
}

Compilation message (stderr)

Main.cpp: In member function 'll Solution::profitProfit()':
Main.cpp:35:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   35 |    auto [diff, x] = arr[curr];
      |         ^

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