oj.uz

Submission #369253

# Submission time Handle Problem Language Result Execution time Memory
369253 2021-02-21T03:44:31 Z chienyu_xiong Journey (NOI18_journey) C++17
69 / 100
 67 ms 30828 KB 
/*
 * CM 	= March
 * M 	= April
 * IM 	= July
 * GM 	= September
 * IGM	= December
*/

#include <bits/stdc++.h>

#define F first
#define S second

#define pb push_back
#define mp make_pair

typedef long long int lli;

#define pll pair<lli, lli>
#define pil pair<int, lli>
#define pli pair<lli, int>
#define pii pair<int, int>
#define pdd pair<double, double>

#define vi vector<int>
#define vl vector<lli>

#define dmx(x, y) x = max(x, y)
#define dmn(x, y) x = min(x, y)

using namespace std;

void setIO(string str, bool dbg) {
	ios_base::sync_with_stdio(0);

	cin.tie(nullptr);
	cout.tie(nullptr);

	if (!dbg) {
		freopen((str + ".in").c_str(), "r", stdin);
		freopen((str + ".out").c_str(), "w", stdout);
	}
}

const int MAX = 1e4 + 5;
const int LEN = 4e2 + 5;
const int LVL = 2e1 + 0;
const lli MOD = 1e9 + 7;
const lli INF = 9e17;

int xyz = 1; // test cases

int n, m, h;
int vst[MAX];
lli dps[MAX][LEN];

vector<pil> con[MAX];

void dfs(int pos) {
	if (pos == n - 1) return;
	
	vst[pos] = true;
	for (auto adj : con[pos]) {
		int nxt = adj.F;
		int val = adj.S;

		if (nxt < pos) continue;
	
		if (!vst[nxt]) dfs(nxt);
		for (int i = val; i < m; i++) {
			dps[pos][i] += dps[nxt][i - val];
			dps[pos][i] = min(dps[pos][i], 500000001LL);
		}
	}
	
	for (int i = 1; i < m; i++)
		dps[pos][i] += dps[pos][i - 1], dmn(dps[pos][i], 500000001LL);
}

void fnc() {
	cin >> n >> m >> h;
	
	for (int i = 0; i < n - 1; i++)
		for (int j = 0; j < h; j++) {
			int pos;
			int val;
			cin >> pos >> val;
			
			con[i].pb({pos, val});
		}
	
	dps[n - 1][0] = 1;
	
	dfs(0);
	
	for (int i = 0; i < m; i++)
		cout << dps[0][i] << " "; cout << "\n";
}

int main() {
	setIO("", 1);

	while (xyz--) fnc();

	return 0;
}

Compilation message

journey.cpp: In function 'void fnc()':
journey.cpp:96:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   96 |  for (int i = 0; i < m; i++)
      |  ^~~
journey.cpp:97:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   97 |   cout << dps[0][i] << " "; cout << "\n";
      |                             ^~~~
journey.cpp: In function 'void setIO(std::string, bool)':
journey.cpp:40:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   40 |   freopen((str + ".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
journey.cpp:41:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   41 |   freopen((str + ".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 1 ms 876 KB Output is correct
6 Correct 1 ms 876 KB Output is correct

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 1 ms 876 KB Output is correct
6 Correct 1 ms 876 KB Output is correct
7 Incorrect 67 ms 30828 KB Output isn't correct
8 Halted 0 ms 0 KB -