Submission #994773

#	Time	Username	Problem	Language	Result	Execution time	Memory
994773		MisalignedDiv	Trains (BOI24_trains)	C++14	100 / 100	229 ms	253988 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 + 9, 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 (curr + diff <= N)            DP[curr] += seq[curr + diff][diff];
				if (curr + diff * (x + 1) <= N)  DP[curr] -= seq[curr + diff * (x + 1)][diff];
				DP[curr] = (DP[curr] % MOD + MOD) % MOD;
			}
			for (int j = 1; j < SQR; j++){
				if (curr + j <= N) seq[curr][j] = (seq[curr + j][j] + DP[curr]) % MOD;
				else               seq[curr][j] = DP[curr];
			}
		}
		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: 8 / 8
• Subtask 2: 13 / 13
• Subtask 3: 16 / 16
• Subtask 4: 34 / 34
• Subtask 5: 29 / 29