Submission #1127176

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127176		abushbandit_	Subway (info1cup19_subway)	C++20	50 / 100	230 ms	327680 KiB

subway

//~ how can i make it 10% more fun?
//~ what it would take for me to enjoy this?

#include <bits/stdc++.h>

using namespace std;
 
#define int long long
#define pb push_back
#define all(x) x.begin(), x.end()
#define ff first
#define ss second
 
template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}
 
template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}
 
int exp(int x, int n, int m) {
	x %= m;
	int res = 1;
	while (n > 0) {
		if (n & 1) { res = (res * x) % m; }
		x = (x * x) % m;
		n >>= 1;
	}
	return res;
}
 
int power(int x, int n) {
	int res = 1;
	while (n > 0) {
		if (n & 1) { res = res * x ; }
		x = x * x ;
		n >>= 1;
	}
	return res;
}
 
const int N = 2e5 + 1;
 
const int mod = 1e9 + 7;
 
const int inf = 1e18;
 
void add(int &a, int b) {
    if (a + b >= mod) a = (a + b) - mod;
    else a += b;
}
 
void sub(int &a, int b) {
    if (a - b < 0) a = (a - b) + mod;
    else a -= b;;
}
 
template<typename T> using matrix = vector<vector<T>>;
 
namespace FAST {
    template<typename T, typename F>
    istream &operator>>(istream &cin, pair<T, F> &p) {
        cin >> p.first >> p.second;
        return cin;
    }
 
    template<typename T, typename F>
    ostream &operator<<(ostream &cout, pair<T, F> &p) {
        cout << p.first << ' ' << p.second;
        return cout;
    }
 
    template<typename T>
    istream &operator>>(istream &cin, vector<T> &a) {
		for (T &i: a) cin >> i;
        return cin;
    }
	
    template<typename T>
    ostream &operator<<(ostream &cout, vector<T> &a) {
        for (T i: a) cout << i << ' ';
        return cout;
    }
 
    template<typename T>
    istream &operator>>(istream &cin, deque<T> &a) {
        for (T &i: a) cin >> i;
        return cin;
    }
 
    template<typename T>
    ostream &operator<<(ostream &cout, deque<T> &a) {
        for (T i: a) cout << i << ' ';
        return cout;
    }
}
using namespace FAST;

void solve() {
	
	int k;
	cin >> k;
	int ans = inf;
	int dp[k + 1];
	for(int i = 0;i <= k;i++) {
		dp[i] = inf;
	}
	dp[0] = 0;
	int tar = 0;
	for(int x = 1; (x * (x - 1)) / 2 <= k; x++) {
		int nk = k;
		k -= (x * (x - 1)) / 2;
		for(int j = 1;j <= x;j++) {
			for(int i = 0;i <= k - j;i++) {
				if(dp[i] != inf) {
					chmin(dp[i + j], dp[i] + 1);
				}
			}	
		}		
		if(chmin(ans, dp[k] + x)) {
			tar = x;
		}
		for(int i = 1;i <= k;i++) dp[i] = inf;
		k = nk;
	}
	cout << ans << "\n";
	int p[k + 1];
	for(int i = 0;i <= k;i++) p[i] = -1;
	vector<pair<int, int>> res;
	res.push_back({0, -1});
	int x = tar;
	for(int i = 1;i < x;i++) {
		res.push_back({i, i - 1});
	}
	k -= (x * (x - 1)) / 2;
	for(int j = 1;j <= x;j++) {
		for(int i = 0;i <= k - j;i++) {
			if(dp[i] != inf) {
				if(chmin(dp[i + j], dp[i] + 1)) {
					p[i + j] = i;
				}
			}
		}	
	}		
	
	
	int v = x;
	
	while(p[k] != -1) {
		int dif = k - p[k];
		res.push_back({v++, dif - 1});
		k = p[k];
	}
	for(auto [a, b] : res) {
		cout << a << " " << b << "\n";
	}
	
} 

signed main() {
	
	ios_base::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	
	int t = 1;
	//~ cin >> t;
	while(t--){
		solve();
	}
	
} 

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 0 / 50