oj.uz

답안 #994772

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
994772 2024-06-08T05:29:37 Z MisalignedDiv Trains (BOI24_trains) C++14
34 / 100
 218 ms 252956 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 + 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 (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;
			}
			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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 131 ms 250908 KB Output is correct
2 Correct 134 ms 250804 KB Output is correct
3 Incorrect 133 ms 250804 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 131 ms 250908 KB Output is correct
2 Correct 134 ms 250804 KB Output is correct
3 Incorrect 133 ms 250804 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 129 ms 250704 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 174 ms 252100 KB Output is correct
2 Correct 160 ms 251988 KB Output is correct
3 Correct 214 ms 252912 KB Output is correct
4 Correct 199 ms 252932 KB Output is correct
5 Correct 133 ms 250704 KB Output is correct
6 Correct 135 ms 250704 KB Output is correct
7 Correct 139 ms 251216 KB Output is correct
8 Correct 218 ms 252956 KB Output is correct

Subtask #5
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 131 ms 250908 KB Output is correct
2 Correct 134 ms 250804 KB Output is correct
3 Incorrect 133 ms 250804 KB Output isn't correct
4 Halted 0 ms 0 KB -