Submission #369252

#	Time	Username	Problem	Language	Result	Execution time	Memory
369252		chienyu_xiong	Journey (NOI18_journey)	C++17	69 / 100	67 ms	30028 KiB

journey

/*
 * 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<pii> 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 (stderr)

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 / 20
• Subtask 2: 23 / 23
• Subtask 3: 26 / 26
• Subtask 4: 0 / 31