oj.uz

Submission #994769

# Submission time Handle Problem Language Result Execution time Memory
994769 2024-06-08T05:07:41 Z MisalignedDiv Trains (BOI24_trains) C++14
0 / 100
 172 ms 251864 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 250796 KB Output is correct
2 Incorrect 128 ms 250692 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 250796 KB Output is correct
2 Incorrect 128 ms 250692 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 132 ms 250740 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 172 ms 251864 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 250796 KB Output is correct
2 Incorrect 128 ms 250692 KB Output isn't correct
3 Halted 0 ms 0 KB -