akhauriyash/Code-Regression huggingface dataset:
from collections import defaultdict, deque
from sys import stdin
N, M = map(int, stdin.readline().split())
x = []
y = []
count_in = defaultdict(int)
graph = [[] for _ in range(N)]
graph = defaultdict(list)
graph_reverse = defaultdict(list)
for _ in range(M):
    tmpx, tmpy = map(int, stdin.readline().split())
    x.append(tmpx-1)
    y.append(tmpy-1)
    graph[tmpx-1].append(tmpy-1)
    graph_reverse[tmpy-1].append(tmpx-1)
    count_in[tmpy-1] += 1
q = deque(v for v in range(N) if count_in[v] == 0)
res = []
while q:
    v = q.popleft()
    res.append(v)
    for v_out in graph[v]:
        count_in[v_out] -= 1
        if count_in[v_out] == 0:
            q.append(v_out)

dp = [0 for _ in range(N)]
dp[0] = 0
point2order = defaultdict(int)
for i in range(N):
    point2order[res[i]] = i
    for v in graph_reverse[res[i]]:
        dp[i] = max(dp[i], dp[point2order[v]]+1)
print(dp[N-1])


Measured memory_bytes: 88016
#include <bits/stdc++.h>
using namespace std;
#define int long long

int my_gcd(int n, int m){
    if(n < m) swap(n, m);
    if(m == 0) return n;
    return my_gcd(m, n%m);
}

signed main(){
    // cout << fixed << setprecision(10) << flush;
    // ここまでの WA はどこで時間がかかっているかの実験です
    // cin が悪そうだという結論が出ました
    cin.tie(0); ios::sync_with_stdio(false);

    int n;
    cin >> n;
    vector<int> a(n);
    int maxa = 0;
    for(int i=0; i<n; i++){
        cin >> a[i];
        maxa = (maxa < a[i])? a[i] : maxa;
    }

    vector<int> primes;
    vector<int> min_prime_factor(maxa+1, 0);
    
    primes.push_back(2);
    for(int j=2; j<=maxa; j+=2){
        min_prime_factor[j] = 2;
    }
    
    int i;
    for(i=3; i*i<=maxa; i+=2){
        if(min_prime_factor[i] != 0) continue;
        primes.push_back(i);
        for(int j=i; j<=maxa; j+=i){
            if(min_prime_factor[j] == 0){
                min_prime_factor[j] = i;
            }
        }
    }
    
    for(; i<=maxa; i+=2){
        if(min_prime_factor[i] == 0){
            primes.push_back(i);
            min_prime_factor[i] = i;
        }
    }
    int ggcd = a[0];
    for(int i=1; i<n; i++){
        ggcd = my_gcd(a[i], ggcd);
        if(ggcd == 1) break;
    }

    if(ggcd != 1){
        cout << "not coprime" << endl;
        return 0;
    }

    map<int, int> mp_prime;
    for(int j=0; j<primes.size(); j++){
        mp_prime[primes[j]] = j;
    }

    vector<bool> c(primes.size(), false);
    for(int i=0; i<n; i++){
        while(a[i] != 1){
            int p = min_prime_factor[a[i]];
            if(c[mp_prime[p]] != false){
                cout << "setwise coprime" << endl;
                return 0;
            }
            c[mp_prime[p]] = true;
            a[i] /= p;
            while(a[i] % p == 0) a[i] /= p;
        }
    }
    cout << "pairwise coprime" << endl;

    return 0;
}

Measured memory_bytes: 24404
#include<bits/stdc++.h>
#include<stdint.h>

using namespace std;


#define MOD 1e9+7
#define ll long long int
#define ff first
#define ss second


template <typename T,typename G>
ostream& operator << (ostream& out, const pair<T,G> &a) 
{return out<<"( "<<a.ff<<", "<<a.ss<<")";}

template <typename T>
ostream& operator << (ostream& out, const vector<T> &a) 
{out<<"[ ";for(const auto &i:a)out<<i<<", ";return out<<"]"<<endl;}

template <typename T>
ostream& operator << (ostream& out, const set<T> &a) 
{out<<"{ ";for(const auto &i:a)out<<i<<", ";return out<<"}"<<endl;}

template <typename T,typename G>
ostream& operator << (ostream& out, const map<T,G> &a) 
{out<<"< ";for(const auto &i:a)out<<i<<", ";return out<<">"<<endl;}

void solve()
{
	ll n;
	cin>>n;
	vector<ll> h(n),c(n);

	for(int i=0;i<n;i++)
		cin>>h[i];
	c[0]=0;
	c[1]=abs(h[1]-h[0]);

	for(int i=2;i<n;i++)
		c[i]=min(abs(h[i]-h[i-1])+c[i-1],abs(h[i]-h[i-2])+c[i-2]);
	cout<<c[n-1];
}


int32_t main()
{
	
	//your code goes here...	
	int t=1;
	//cin>>t;
	while(t--)
	{
	    solve();
	}	
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define rp(i,n) for(int i=0; i<n; i++)
using namespace std;
using ll=long long;
using P=pair<int,int>;
using G=vector<vector<int>>;

int main(){
    int n,m;
    cin >> n >> m;
    int jogen=m/n;
    int ans=0;
    for(int i=1; i<=min((int)sqrt(m),jogen); i++){
        if(m%i==0) {
            ans=i;
            if(m/i<=jogen){
                ans=m/i;
                break;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <math.h>
#define MOD 1000000007
typedef long long ll;
using namespace std;

int m[9][9];
int n,M;
int p[9];
int ans=0;

void dfs(int x,int d){
  p[x]=1;
  for(int i=1;i<=n;i++){
    if(m[x][i]==0) continue;
    if(p[i]==1) continue;
    dfs(i,d+1);
  }
  if(d==n) ans++;
  p[x]=0;
}

int main(){
  cin>>n>>M;
  int a,b;

  for(int i=0;i<M;i++){
    cin>>a>>b;
    m[a][b]=1;
    m[b][a]=1;
  }

  dfs(1,1);
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
using namespace std;

int main()
{
    //freopen("dulieuvao.inp","r",stdin);
    long long int n,w;
    cin>>n>>w;
    long long int f[n+1][w+1],m[n+1],v[n+1];
    for(int i=0;i<=n;i++)
    {
        f[i][0]=0;
    }
    for(int i=0;i<=w;i++)
    {
        f[0][i]=0;
    }
    for(int i=1;i<=n;i++)
    {
        cin>>m[i]>>v[i];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=w;j++)
        if(m[i]<=j)
        {
            f[i][j]=max(f[i-1][j-m[i]]+v[i],f[i-1][j]);
        }
        else
        {
            f[i][j]=f[i-1][j];
        }
    }
    cout<<f[n][w]<<endl;
}


Measured memory_bytes: 79104
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main() {
  int n;
  cin >> n;
  long long int sum = 0;
  rep(i,n+1) {
    if (i%3!=0 && i%5!=0) sum += i;
  }

  cout << sum << endl;
}


Measured memory_bytes: 3640
n = int(input())
As = list()
for i in range(n):
    a = int(input())
    As.append(a)

max_left = list()
max_right = list()

for i in range(n):
    if i == 0:
        max_left.append(As[i])
        max_right.append(As[-1 - i])
    
    else:
        max_left.append(max(max_left[-1], As[i]))
        max_right.append(max(max_right[-1], As[-1-i]))

max_right.reverse()

for i in range(n):
    if i == 0:
        print(max_right[i + 1])
    elif i == n - 1:
        print(max_left[i - 1])
    else:
        print(max(max_left[i - 1], max_right[i + 1]))


Measured memory_bytes: 15692
#include <bits/stdc++.h>
#include<string.h>
using namespace std;
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define Max(x,y,z) max(x,max(y,z))
#define Min(x,y,z) min(x,min(y,z))
#define fr(i,s,e) for(i=s;i<e;i++)
#define rf(i,s,e) for(i=s-1;i>=e;i--)
#define pb push_back
#define eb emblace_back
#define mp make_pair
#define ff first
#define ss second
//#define int   long long
#define ll   long long
#define trace1(x)                cerr<<#x<<": "<<x<<endl
#define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
#define vl vector<long long>
#define inf (1LL<<61)
#define vi vector<int>
#define vii vector< vector<int> >
#define vll vector< vector<long long> >
#define vpi vector< pair<int,int> >
#define vpl vector< pair<ll,ll> >
#define viii vector< vector<vector<int> > >
typedef pair<pair<int, int>,int> P;
#define cd complex<double>
#define PI 4*atan(1)
#define mod %1000000007
#define pi 3.14159265358979323846//20 decimals
#define ld long double

ll n, m;
vl ad[100002];
ll vis[100002];
ll lp[100002];

void dfs(ll i)
{
	ll j;
	fr(j,0,ad[i].size())
	{
		if(vis[ad[i][j]] == 0)
			dfs(ad[i][j]);
		
	}
	ll mx = 0;
	fr(j,0,ad[i].size())
		if(mx < lp[ad[i][j]])
			mx = lp[ad[i][j]];
	lp[i] = 1 + mx;
	vis[i] = 1;
}
	
int main()
{
	FAST;
	ll i, j;
	cin >> n >> m;
	fr(i,0,m)
	{
		ll t1, t2;
		cin >> t1 >> t2;
		ad[t1].pb(t2);
	}
	for(j = 1;j < n+1;j++)
	{
		if(vis[j] == 0)
			dfs(j);
	}
	ll mx = 0;
	fr(j,1,n+1)
		mx = max(mx, lp[j]);
	cout << mx - 1;
}


Measured memory_bytes: 9344
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
using ll = long long;
#define rep(i, j, n) for(int i = (j); i < (n); ++i)
#define rrep(i, j, n) for(int i = (n) - 1; (j) <= i; --i)
constexpr ll INF = 1LL << 60;

int main() {
	int n; cin >> n;
	vector<ll> a(n * 3); 
	rep(i, 0, n * 3) cin >> a[i];

	// 前半、後半同時にやろうとすると後半の下位n個の更新がむずい(これができるやばいデータ構造はありそう)
	// 別々にやって結果を配列に保持しておく

	ll left_sum = 0;
	ll right_sum = 0;
	priority_queue<ll, vector<ll>, greater<ll>> left;
	priority_queue<ll> right;
	// 
	vector<ll> left_res(n + 1);
	vector<ll> right_res(n + 1);

	// left
	rep(i, 0, n) {
		left.push(a[i]);
		left_sum += a[i];
	}
	rep(i, n, n * 2 + 1) {
		left_res[i - n] = left_sum;
		left.push(a[i]);
		left_sum += a[i];
		left_sum -= left.top();
		left.pop();
	}

	// right
	rep(i, n * 2, n * 3) {
		right.push(a[i]);
		right_sum += a[i];
	}
	rrep(i, n - 1, n * 2) {
		right_res[i - n + 1] = right_sum;
		right.push(a[i]);
		right_sum += a[i];
		right_sum -= right.top();
		right.pop();
	}

	ll ans = -INF;
	rep(i, 0, n + 1)
		ans = max(ans, left_res[i] - right_res[i]);
	cout << ans;
	return 0;
}

Measured memory_bytes: 9524
A1 = list(map(int, input().split()))
A2 = list(map(int, input().split()))
A3 = list(map(int, input().split()))
N = int(input())
b = []
for i in range(N):
    inputItem = int(input())
    b.append(inputItem)
check = {'first':[False,False,False],'second':[False,False,False],'third':[False,False,False]}
for j in b:
    if j in A1:
        pos = A1.index(j)
        check['first'][pos] = True
    elif j in A2:
        pos = A2.index(j)
        check['second'][pos] = True
    elif j in A3:
        pos = A3.index(j)
        check['third'][pos] = True

bingo = False
for k in range(3):
    if check['first'][k]==check['second'][k]==check['third'][k]==True:
        bingo = True
        break
if check['first'][0]==check['first'][1]==check['first'][2]==True:
    bingo = True
elif check['second'][0]==check['second'][1]==check['second'][2]==True:
    bingo = True
elif check['third'][0]==check['third'][1]==check['third'][2]==True:
    bingo = True
if check['first'][0]==check['second'][1]==check['third'][2]==True or check['first'][2]==check['second'][1]==check['third'][0]==True:
    bingo = True
if bingo:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3316
#include <bits/stdc++.h>
using namespace std;

int main() {
	vector<int> a(300, 0);
	char t;
	for (int i = 0; i < 4; i++)
	{
		cin >> t;
		a[t]++;
	}
	for (int i = 0; i < 300; i++)
	{
		if (a[i] != 0 && a[i] != 2)
		{
			cout << "No";
			return 0;
		}
	}
	cout << "Yes";
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#define MAX 15
using namespace std;

int main(){
	int n;
	
	while(scanf("%d", &n) != EOF){
		int array[MAX][MAX];
		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
				array[i][j] = 0;
	
		int j = n / 2 + 1, k = n / 2;
		for(int i = 1; i <= n * n; i++){
			if(j >= n) j = 0;
			if(k >= n) k = 0;
			if(array[j][k] > 0){
				j++;
				k--;
				if(j >= n) j = 0;
				if(k >= n) k = 0;
				if(j < 0)  j = n - 1;
				if(k < 0)  k = n - 1;
				array[j][k] = i;
				j++;
				k++;
				continue;
			}
			array[j][k] = i;
			j++;
			k++;
		}
	
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				printf("%4d", array[i][j]);
			}
			printf("\n");
		}
	}
	return 0;
}

Measured memory_bytes: 1044
n = int(input())
a = list(map(int, input().split()))
q = int(input())
m = list(map(int, input().split()))
memory = [[-1 for i in range(max(m)+1)]for j in range(n)]

def f(i, m):
    if m == 0:
        return 1
    elif i >= n:
        return 0
    elif memory[i][m] != -1:
        return memory[i][m]
    elif m - a[i] >= 0:
        res0 = f(i+1, m)
        res1 = f(i+1, m-a[i])
        if res0 or res1:
            memory[i][m] = 1
            return 1
        else:
            memory[i][m] = 0
            return 0
    else:
        res = f(i+1, m)
        memory[i][m] = res
        return res

for k in m:
    print('yes' if f(0, k) else 'no')



Measured memory_bytes: 5948
#include <iostream>
#include <cstdlib>

using namespace std;

int main(void)
{
    int n;
    cin >> n;

    int a;
    int count[n] = {0};
    for(int i = 1; i < n; i ++)
    {
        cin >> a;
        count[a - 1] ++;
    }

    for(int i = 0; i < n; i ++)
        cout << count[i] << endl;

    return 0;
}

Measured memory_bytes: 4416
// AOJ 2578 Disciple Life is Hard
// 2018.3.16 bal4u

#include <stdio.h>
#include <string.h>

// library //
//#define getchar_unlocked()  getchar()
int in()
{
	int n = 0, c = getchar_unlocked();
	do n = (n<<3)+(n<<1) + (c & 0xf), c = getchar_unlocked(); while (c >= '0');
	return n;
}

// library //

int e[102], c[102], h[102], a[102];
int p[102];
int dp1[102][102*102], dp2[102][102][102], dp3[102][102];

int main()
{
	int S, T, U, N, O, D, i, j, s, x;

	S = in(), T = in(), U = in(), N = in(), O = in(), D = in();
	for (i = 0; i < T; i++) e[i] = in(), c[i] = in();
	for (i = 0; i < N; i++) h[i] = in(), a[i] = in();

	memset(dp1, -1, sizeof(dp1)), dp1[0][0] = 0;
	for (i = 1; i <= N; i++) for (j = 0; j <= 10000; j++) for (s = 0; s*a[i-1] <= j; s++) {
		if (dp1[i-1][j-s*a[i-1]] >= 0) {
			x = dp1[i-1][j-s*a[i-1]]+h[i-1]*s;
			if (dp1[i][j] < x) dp1[i][j] = x;
		}
	}

	memset(dp2, -1, sizeof(dp2)); dp2[0][0][0] = 0;
	for (i = 1; i <= T; i++) {
		dp2[i][0][0] = 0;
		for (j = 1; j <= i; j++) for (s = 0; s <= S; s++) {
			dp2[i][j][s] = dp2[i-1][j][s];
			if (s-e[i-1] >= 0 && dp2[i-1][j-1][s-e[i-1]] >= 0) {
				x = dp2[i-1][j-1][s-e[i-1]]+c[i-1];
				if (dp2[i][j][s] < x) dp2[i][j][s] = x;
			}
		}
	}

	memset(p, -1, sizeof(p));
    for (s = 0; s <= S; s++) for (i = 0; i <= dp2[T][U][s]; i++) if (p[s] < dp1[N][i]) p[s] = dp1[N][i];

	memset(dp3, -1, sizeof(dp3)), memset(dp3[0], 0, sizeof(dp3[0]));
	for (i = 1; i <= D; i++) for (s = 0; s <= S; s++) for (j = 0; j <= s; j++) {
		x = s-j+O; if (x > S) x = S;
		if (dp3[i-1][x] >= 0 && p[j] >= 0) {
			int t = dp3[i-1][x] + p[j];
			if (dp3[i][s] < t) dp3[i][s] = t;
		}
	}
	printf("%d\n", dp3[D][S]);
}


Measured memory_bytes: 10160
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main() {
  int H, W, K, p{1};
  cin >> H >> W >> K;
  vector<bool> v(H);
  vector<string> s(H);
  vector<vector<int>> g(H,vector<int>(W));
  for (auto &x: s) {
    cin >> x;
  }
  for (int i = 0; i != H; ++i) {
    int c = std::count(begin(s[i]), end(s[i]), '#');
    if (!c) {
      v[i] = 1;
      continue;
    }
    for (int j = 0; j != W; ++j) {
      g[i][j] = p;
      if (s[i][j] == '#' && --c) ++p;
    }
    ++p;
  }

  for (int i = 0; i != H; ++i) {
    if (!v[i]) continue;
    auto h = find(begin(v)+i, end(v), 0);
    if (h == end(v)) {
      h = find(rbegin(v)+(H-i-1), rend(v), 0).base() - 1;
    }
     copy(g[h-begin(v)].begin(), g[h-begin(v)].end(), g[i].begin());
    v[i] = false;
  }

  for (auto x: g) {
    for (int j = 0; j != W; ++j) {
      cout << (j?" ":"") << x[j];
    }
    cout << endl;
  }
}


Measured memory_bytes: 4104
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int i=(a),_ed=(b);i<=_ed;++i)
#define DREP(i,a,b) for(int i=(a),_ed=(b);i>=_ed;--i)
#define mp(x,y) make_pair((x),(y))
#define sz(x) (int)(x).size()
#define pb push_back
typedef long long ll;
typedef pair<int,int> pii;
inline int read(){
    register int x=0,f=1;register char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=0;ch=getchar();}
    while(isdigit(ch)){x=x*10+(ch^'0');ch=getchar();}
    return f?x:-x;
}

const int mod=1e9+7;
int N,f[1000005];
inline void inc(int& x,int y){x=x+y<mod?x+y:x+y-mod;}

int main(){
	// freopen("in.in","r",stdin);
	N=read();
	f[0]=0,f[1]=N;
	REP(i,2,N){
		inc(f[i],(f[i-1]-f[i-2]+mod)%mod);
		inc(f[i],N-max(1,i-2));
		if(i>=3)inc(f[i],f[i-3]);
		inc(f[i],1ll*(N-1)*(N-1)%mod);
		inc(f[i],f[i-1]);
	}
	printf("%d\n",(f[N]-f[N-1]+mod)%mod);
	return 0;
}


Measured memory_bytes: 4096
#include<bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pair<int, int> > vii;
#define rrep(i, m, n) for(int (i)=(m); (i)<(n);  (i)++)
#define erep(i, m, n) for(int (i)=(m); (i)<=(n); (i)++)
#define  rep(i, n)    for(int (i)=0; (i)<(n);  (i)++)
#define rrev(i, m, n) for(int (i)=(n)-1; (i)>=(m); (i)--)
#define erev(i, m, n) for(int (i)=(n); (i)>=(m); (i)--)
#define  rev(i, n)    for(int (i)=(n)-1; (i)>=0; (i)--)
#define vrep(i, c)    for(__typeof((c).begin())i=(c).begin(); i!=(c).end(); i++)
#define  ALL(v)       (v).begin(), (v).end()
#define mp            make_pair
#define pb            push_back
template<class T, class S> inline bool minup(T& m, S x){ return m>(T)x ? (m=(T)x, true) : false; }
template<class T, class S> inline bool maxup(T& m, S x){ return m<(T)x ? (m=(T)x, true) : false; }

const int    INF = 1000000000;
const ll     MOD = 1000000007LL;
const double EPS = 1E-12;

template<typename T> ostream& operator <<(ostream& r, const vector<T> t){vrep(v,t)r<<*v<<(v+1==t.end()?"":" ");return r;}
template<typename T> ostream& operator <<(ostream& r, const pair<vector<T>, int> p){int n=p.second;minup(n,p.first.size());rep(i,n-1)r<<p.first[i]<<' ';r<<p.first[n-1];return r;}
template<typename T> ostream& operator <<(ostream& r, const pair<T*, int> p){int n=p.second-1;rep(i,n)r<<p.first[i]<<' ';return r<<p.first[n];}
template<typename T, size_t S> ostream& operator <<(ostream& r, const T (&a)[S]){rep(i,S-1)r<<a[i]<<' ';return r<<a[S-1];}


int n, r;
int x, y;

int main()
{
  while((cin >> n >> r) && n){
    vi card(n);
    rep(i, n) card[i] = n - i;
    while(r--){
      cin >> x >> y;
      x -= 1;
      vi tmp;
      erep(i, x, x + y) tmp.pb(card[i]);
      rev(i, x) card[i + y] = card[i];
      rep(i, y) card[i] = tmp[i];
    }
    cout << card[0] << endl;
  }

  return 0;
}

Measured memory_bytes: 1220
n = int(input())
c = [0, 0, 0, 0]
for i in range(n):
  judge = input()
  if judge == 'AC':
    c[0] = c[0] + 1
  if judge == 'WA':
    c[1] = c[1] + 1
  if judge == 'TLE':
    c[2] = c[2] + 1
  if judge == 'RE':
    c[3] = c[3] + 1
print('AC x',c[0])
print('WA x',c[1])
print('TLE x',c[2])
print('RE x',c[3])

Measured memory_bytes: 9216
#include <bits/stdc++.h>
using namespace std;

int N, X, D;
#define MAXN 50
long long M[MAXN];
vector<int> K[MAXN];
typedef tuple<long long, int, int, int> T;
T I[MAXN];
long long DP[MAXN * MAXN * MAXN + 1];
#define INF INT_MAX
int R;

T subtree(int v) {
  T res(M[v], 1,
    v == 0 ? N : min(D, N),
    v == 0 ? INF : D - min(D, N));
  for(int w : K[v]) {
    auto t = subtree(w);
    get<0>(res) += get<0>(t); get<1>(res) += get<1>(t);
  }
  I[v] = res;
  return res;
}
bool compare(const T& t1, const T& t2) {
  return get<1>(t1) * get<0>(t2) > get<1>(t2) * get<0>(t1);
}
int main() {
  cin >> N >> X >> D;
  for(int i = 0; i < N; ++i) {
    cin >> M[i];
    if(i > 0) {
      int p; cin >> p; --p;
      K[p].push_back(i);
    }
  }
  subtree(0);
  sort(I, I + N, compare);
  fill(DP, DP + N * N * N + 1, INF);
  DP[0] = 0;
  for(int i = 0; i < N; ++i) {
    int rem = get<2>(I[i]);
    for(int k = 0; rem > 0; ++k) {
      int n = min(rem, 1 << k); rem -= n;
      long long dmass = n * get<0>(I[i]); int dvalue = n * get<1>(I[i]);
      for(int value = N * N * N; value >= dvalue; --value) {
        if(DP[value - dvalue] != INF) {
          DP[value] = min(DP[value], DP[value - dvalue] + dmass);
        }
      }
    }
  }
  for(int value = 0; value <= N * N * N; ++value) {
    if(DP[value] > X) continue;
    int lmass = X - DP[value];
    int rvalue = value;
    for(int i = 0; i < N && lmass > 0; ++i) {
      int n = min<long long>(get<3>(I[i]), lmass / get<0>(I[i]));
      long long dmass = n * get<0>(I[i]), dvalue = n * get<1>(I[i]);
      lmass -= dmass; rvalue += dvalue;
    }
    R = max(R, rvalue);
  }
  cout << R << endl;
  return 0;
}


Measured memory_bytes: 1280
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define pdd pair<double,double>
using namespace std;
int a[10005],b[10005];
int main(){
    int N;
    scanf("%d",&N);
    long long t1=0,t2=0;
    for(int i=0;i<N;i++)scanf("%d",&a[i]);
    for(int i=0;i<N;i++)scanf("%d",&b[i]);
    for(int i=0;i<N;i++)
    {
        if(a[i]>b[i])t1=t1+(a[i]-b[i]);
        else t2=t2+(b[i]-a[i])/2;
    }
    if(t2<t1)printf("No\n");
    else printf("Yes\n");
    return 0;
}
/*
1 1 2 2
2
2 0 1
1 1 1
*/


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < n; i++)
  
int main(){
  int n, m;
  vector<string> r(100);
  vector<string> b(100);
  cin >> n;
  rep(i,n){
    cin >> r.at(i);
  }
  cin >> m;
  rep(i,m){
    cin >> b.at(i);
  }
  int cMax = 0;
  int count;
  rep(i,n){
    count = 0;
    rep(j,n){
      if(r.at(j) == r.at(i)) count++;
    }
    rep(j,m){
      if(b.at(j) == r.at(i)) count--;
    }
    cMax = max(cMax, count);
  }
  cout << cMax << endl;
}



Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>	
#include<cmath>
using namespace std;
int main() {
	int n; string s; cin >> s;
	if (s == "AKIHABARA") { cout << "YES" << endl; }
	else if (s == "AKIHABAR") { cout << "YES" << endl; }
	else if (s == "AKIHABRA") { cout << "YES" << endl; }
	else if (s == "AKIHBARA") { cout << "YES" << endl; }
	else if (s == "KIHABARA") { cout << "YES" << endl; }
	else if (s == "KIHBARA") { cout << "YES" << endl; }else if (s == "KIHBRA") { cout << "YES" << endl; }
	else if (s == "KIHABRA") { cout << "YES" << endl; }else if (s == "KIHBAR") { cout << "YES" << endl; }
	else if (s == "KIHABAR") { cout << "YES" << endl; }else if (s == "KIHABR") { cout << "YES" << endl; }
	else if (s == "AKIHBRA") { cout << "YES" << endl; }else if (s == "AKIHBR") { cout << "YES" << endl; }
	else if (s == "AKIHBAR") { cout << "YES" << endl; }else if (s == "KIHBR") { cout << "YES" << endl; }
	else if (s == "AKIHABR") { cout << "YES" << endl; }
	else { cout << "NO" << endl; }
	cin >> n;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
	ll n, k; cin >> n >> k;
	ll cnt = 0;
	if (!k) cnt = n * n;
	else {
		for (int b = k + 1; b <= n; b++) {
			ll div = n / b;
			ll rem = n % b;
			cnt += div * max(0LL, b - k) + max(0LL, rem - k + 1);
		}
	}
	cout << cnt << '\n';
    return 0;
}


Measured memory_bytes: 3584
#include<bits/stdc++.h>
using namespace std;

#define ALL(a)  (a).begin(),(a).end()
#define ALLR(a)  (a).rbegin(),(a).rend()
#define spa << " " <<
#define lfs <<fixed<<setprecision(10)<<
#define test cout<<"test"<<endl;
#define fi first
#define se second
#define MP make_pair
#define rep(i,n,m) for(ll i = n; i < (ll)(m); i++)
#define rrep(i,n,m) for(ll i = n - 1; i >= (ll)(m); i--)
typedef long long ll;
typedef long double ld;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const ll INF = 1e18;
using P = pair<ll, ll>;
template<typename T>
void chmin(T &a,T b){if(a>b)a=b;}
template<typename T>
void chmax(T &a,T b){if(a<b)a=b;}
void pmod(ll &a,ll b){a=(a+b)%MOD;}
void pmod(ll &a,ll b,ll c){a=(b+c)%MOD;}
void qmod(ll &a,ll b){a=(a*b)%MOD;}
void qmod(ll &a,ll b,ll c){a=(b*c)%MOD;}
ll median(ll a,ll b, ll c){return a+b+c-max({a,b,c})-min({a,b,c});}
void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
template<typename T1,typename T2>
void ans(bool x,T1 y,T2 z){if(x)cout<<y<<endl;else cout<<z<<endl;}  
template<typename T>
void debug(vector<vector<T>>v,ll h,ll w){for(ll i=0;i<h;i++)
{cout<<v[i][0];for(ll j=1;j<w;j++)cout spa v[i][j];cout<<endl;}};
void debug(vector<string>v,ll h,ll w){for(ll i=0;i<h;i++)
{for(ll j=0;j<w;j++)cout<<v[i][j];cout<<endl;}};
template<typename T>
void debug(vector<T>v,ll n){cout<<v[0];
for(ll i=1;i<n;i++)cout spa v[i];cout<<endl;};
template<typename T>
vector<vector<T>>vec(ll x, ll y, T w){
  vector<vector<T>>v(x,vector<T>(y,w));return v;}
ll gcd(ll x,ll y){ll r;while(y!=0&&(r=x%y)!=0){x=y;y=r;}return y==0?x:y;}
template<typename T>
void emp(map<T,ll>&m, T x){m.emplace(x,0).first->second++;}

int main(){
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);
  ll res=0,res1=INF,res2=-INF,buf=0;
  bool judge = true;
  ll n;cin>>n;
  vector<ll>a(n);
  rep(i,0,n)cin>>a[i];
  vector<ll>ret;
  vector<ll>sum(2,-INF);
  rep(i,0,n){
    if(a[i]>=0){
      if(sum[i%2]==-INF)sum[i%2]=a[i];
      else sum[i%2]+=a[i];
    }
  }
  if(sum[0]==-INF&&sum[1]==-INF){
    ll maxbuf=-INF,idx;
    rep(i,0,n){
      if(maxbuf<a[i]){
        maxbuf=a[i];
        idx=i;
      }
    }
    rrep(i,n,idx+1)ret.push_back(i+1);
    rep(i,0,idx)ret.push_back(1);
    cout<<maxbuf<<endl;
    cout<<ret.size()<<endl;
    rep(i,0,ret.size())cout<<ret[i]<<endl;
  }
  else{
    buf=0;
    function<ll(ll)> f=[](ll a){return 2*a;};
    if(sum[0]<sum[1]){
      ret.push_back(1);
      f=[](ll a){return 2*a+1;};
      //cout<<buf spa ret.size()<<endl;
    }
    for(ll i=0;f(i)<n;i++){
      if(a[f(i)]>=0){
        if(buf==0)buf++;
        else ret.push_back(2);
      }
      else{
        if(buf==0){
          ret.push_back(1);
          ret.push_back(1);
        }
        else {
          ret.push_back(3);
          if(f(i)==n-1)ret.push_back(2);
        }
      }
    }
    if(sum[0]<sum[1]&&n%2==1)ret.push_back(2);
    if(sum[0]>=sum[1]&&n%2==0)ret.push_back(2);
    cout<<max(sum[0],sum[1])<<endl;
    cout<<ret.size()<<endl;
    rep(i,0,ret.size())cout<<ret[i]<<endl;
  }

  
  return 0;
}

Measured memory_bytes: 256
//#include<bits/stdc++.h>
#include<iostream>
#include<vector>
#include<algorithm>
#define INF 2147483647
#define lli long long int
#define MOD 1000000007
#define pb push_back

using namespace std;
typedef vector<int> vi;
typedef vector< vector<int> > vvi;
typedef pair<int,int> pii;
typedef vector<pair<int,int>> vpii;

void printv(vvi v){
	for(int i = 0; i < v.size(); i++){
		for(int j = 0; j < v.size(); j++){
			cout << v[i][j] << " ";
		}
		cout << endl;
	}
	return ;
}

int main() {

	int n,m; cin >> n >> m;
	vvi d(n,vi(n,MOD));
	vvi edge(n,vi(n,MOD));
	vvi used(n,vi(n,1));
	for (int i = 0; i < m; i++) {
		int a,b,c; cin >> a >> b >> c;
		d[a-1][b-1] = c;
		d[b-1][a-1] = c;
		edge[a-1][b-1] = c;
		edge[b-1][a-1] = c;
		used[a-1][b-1] = 0;
		used[b-1][a-1] = 0;
	}

	for (int i = 0; i < n; i++) {
		d[i][i] = 0;
	}

	for (int k = 0; k < n; k++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
			}
		}
	}
	
	//printv(d);
	int ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (d[i][j] == edge[i][j]) {
				used[i][j] = 1;
			}
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (used[i][j] == 0) {
				ans++;
				//cout << i << " " << j << endl;
			}
		}
	}
	cout << ans/2 << endl;



	
	return 0;
}





Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i, n) for(int i = 0; i < n; i++)

int main(){
    int N, K;
    cin >> N >> K;
    vector<int> a(N);
    rep(i, N) cin >> a[i];
    vector<int> time(N-K+1);
    for(int i = 0; (i+K-1) < N; i++){
        int left = i;
        int right = i+K-1;
        time[left] = a[right] - a[left];
        time[left] += min(fabs(a[left]), fabs(a[right]));
    }
    sort(time.begin(), time.end());
    int ans = time[0];

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3736
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <random>
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if(a < b){ a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if(a > b){ a = b; return 1; } return 0; }
typedef long long ll;
ll rand26() {
  random_device rnd;
  mt19937 mt(rnd());
  uniform_real_distribution<> rand(0, 25);
  return (ll)rand(mt);
}
int main()
{
  ll D; cin >> D;
  vector<ll> c(26);
  rep(i,26) cin >> c[i];
  vector<vector<ll>> s(D, vector<ll>(26));
  rep(i,D) {
    rep(j,26) {
      cin >> s[i][j];
    }
  }
  vector<ll> t(D);
  rep(i,D) {
    t[i] = rand26();
  }
  // ll m; cin >> m;
  // vector<ll> d(m), q(m);
  // rep(i,m) {
  //   cin >> d[i] >> q[i];
  //   d[i]--; q[i]--;
  // }
  
  vector<set<int>> st(26);
  rep(i,26) {
    st[i].insert(-1);
    st[i].insert(D);    
  }
  rep(i,D) {
    st[t[i]].insert(i);
  }

  ll res = 0;
  // ペナルティ
  vector<ll> pen(26, 0);
  rep(i,26) {
    auto it = st[i].begin();
    it++;
    while(it != st[i].end()) {
      auto it2 = it;
      it2--;
      ll x = *it - *it2 - 1;
      res -= x * (x + 1) / 2 * c[i];
      pen[i] += x * (x + 1) / 2 * c[i];
      it++;
    }
  }
  rep(i,D) {
    res += s[i][t[i]];
  }

  // rep(i,m) {
  //   ll old = t[d[i]];
  //   ll neww = q[i];
  //   res += s[d[i]][neww] - s[d[i]][old];
  //   st[old].erase(d[i]);
  //   st[neww].insert(d[i]);    
  //   // old
  //   res += pen[old];
  //   pen[old] = 0;
  //   auto it = st[old].begin();
  //   it++;
  //   while(it != st[old].end()) {
  //     auto it2 = it;
  //     it2--;
  //     ll x = *it - *it2 - 1;
  //     res -= x * (x + 1) / 2 * c[old];
  //     pen[old] += x * (x + 1) / 2 * c[old];
  //     it++;
  //   }
  //   // new
  //   res += pen[neww];
  //   pen[neww] = 0;
  //   it = st[neww].begin();
  //   it++;
  //   while(it != st[neww].end()) {
  //     auto it2 = it;
  //     it2--;
  //     ll x = *it - *it2 - 1;
  //     res -= x * (x + 1) / 2 * c[neww];
  //     pen[neww] += x * (x + 1) / 2 * c[neww];
  //     it++;
  //   }
  //   t[d[i]] = neww;
  //   cout << res << "\n";
  // }

  rep(i,D) cout << t[i]+1 << "\n";
  
  return 0;
}


Measured memory_bytes: 3704
from collections import deque
x,y,a,b,c = map(int,input().split())
P = deque(sorted(list(map(int,input().split())),reverse=True)[:x])
Q = deque(sorted(list(map(int,input().split())),reverse=True)[:y])
R = deque(sorted(list(map(int,input().split())),reverse=True))
p = P.pop()
q = Q.pop()
r = R.popleft()
ans = 0

while p < r or q < r:
    ans += r
    if len(R) != 0:   
        r = R.popleft()
    else:
        r = 0
    if p < q:
        if len(P) != 0:   
            p = P.pop()
        else:
            p = 10**10
    else:
        if len(Q) != 0:   
            q = Q.pop()
        else:
            q = 10**10
            
ans += sum(P)+sum(Q)
if p != 10**10:
    ans += p
if q != 10**10:
    ans += q
print(ans)

Measured memory_bytes: 23008
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <memory.h>
#include <iomanip>
#include <bitset>
#include <list>
#include <stack>
#include <deque>

using namespace std;

#define mod 1000000007

int main()
{
	int n, m;
	cin >> n >> m;
	vector<pair<int, int> > v;
	for(int i = 0; i < m; i++){
		int a, b;
		cin >> a >> b;
		v.push_back(make_pair(b, a));
	}
	sort(v.begin(), v.end());
	int ans = 0;
	int rightestbridge = -1;
	for(int i = 0; i < m; i++){
		int a = v[i].second;
		int b = v[i].first;
		if(rightestbridge < a){
			ans++;
			rightestbridge = b - 1;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 1400
#include <bits/stdc++.h>
using namespace std;

using int32 = int_fast32_t;
using int64 = int_fast64_t;

const int32 INF = 1e9;
const int32 MOD = 1e9+7;
const int64 LLINF = 1e18;

#define YES(n) cout << ((n) ? "YES\n" : "NO\n"  )
#define Yes(n) cout << ((n) ? "Yes\n" : "No\n"  )
#define POSSIBLE cout << ((n) ? "POSSIBLE\n" : "IMPOSSIBLE\n"  )
#define ANS(n) cout << (n) << "\n"
#define REP(i,n) for(int64 i=0;i<(n);++i)
#define FOR(i,a,b) for(int64 i=(a);i<(b);i++)
#define FORR(i,a,b) for(int64 i=(a);i>=(b);i--)
#define ALL(obj) (obj).begin(),(obj).end()
#define pii pair<int32,int32>
#define pll pair<int64,int64>
#define pb(a) push_back(a)

template<int64 mod>
struct ModInt{
  int64 x;
  constexpr ModInt(int64 y = 0):x((y%mod+mod)%mod){}
  constexpr ModInt& operator+=(const ModInt& a){
    if((x += a.x) >= mod) x -= mod;
    return *this;
  }
  constexpr ModInt& operator-=(const ModInt& a){
    if((x -= a.x) < 0)x += mod;
    return *this;
  }
  constexpr ModInt& operator*=(const ModInt& a){
    x = x * a.x % mod;
    return *this;
  }
  constexpr ModInt& operator/=(const ModInt& a){
    *this *= a.inv();
    return *this;
  }
  constexpr ModInt operator-() const {
    return ModInt(-x);
  }
  constexpr ModInt operator+(const ModInt& a) const {
    return ModInt(*this) += a;
  }
  constexpr ModInt operator-(const ModInt& a) const {
    return ModInt(*this) -= a;
  }
  constexpr ModInt operator*(const ModInt& a) const {
    return ModInt(*this) *= a;
  }
  constexpr ModInt operator/(const ModInt& a) const {
    return ModInt(*this) /= a;
  }
  constexpr ModInt operator++(){
    *this += ModInt(1);
    return *this;
  }
  constexpr ModInt operator++(int){
    ModInt old = *this;
    ++*this;
    return old;
  }
  constexpr ModInt operator--(){
    *this -= ModInt(1);
    return *this;
  }
  constexpr ModInt operator--(int){
    ModInt old = *this;
    --*this;
    return old;
  }
  constexpr bool operator==(const ModInt& a) const {
    return x == a.x;
  }
  constexpr bool operator!=(const ModInt& a) const {
    return x != a.x;
  }
  constexpr ModInt pow(int64 r) const {
    if(!r)return 1;
    ModInt res = pow(r>>1);
    res *= res;
    if(r & 1) res *= *this;
    return res;
  }
  constexpr ModInt inv() const {
    return pow(mod-2);
  }
  friend istream& operator>>(istream& is, ModInt& a){
    int64 t;
    is >> t;
    a = ModInt(t);
    return is;
  }
  friend ostream& operator<<(ostream& os, const ModInt& a){
    return os << a.x;
  }
};
using mint = ModInt<MOD>;

vector<mint> fact, revfact;

mint comb(int32 a, int32 b){
  return fact[a] * revfact[b] * revfact[a-b];
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int32 h,w,a,b;
  cin >> h >> w >> a >> b;
  fact.resize(h+w);
  revfact.resize(h+w);
  fact[0] = 1;
  REP(i,h+w-1)fact[i+1] = fact[i] * (mint)(i+1);
  revfact[h+w-1] = fact[h+w-1].inv();
  FORR(i,h+w-2,0)revfact[i] = revfact[i+1] * (mint)(i+1);
  mint ans = 0;
  REP(i,h-a){
    ans += comb(b-1+i,i) * comb(w-b-1+h-i-1,h-i-1);
  }
  ANS(ans);
  return 0;
}

Measured memory_bytes: 3328
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, M = MAP()

# (鍵の購入コスト, 開けられる宝箱)
keys = [None] * M
for i in range(M):
    c, _ = MAP()
    # どの宝箱を開けられるのかをbitで持っておく
    s = 0
    for a in [a-1 for a in LIST()]:
        s += 1 << a
    keys[i] = (c, s)

# dp[i][j] := i個目の鍵まで見て、集合jの宝箱を開けるための最小コスト
dp = list2d(2, 1<<N, INF)
dp[0][0] = 0
for i in range(M):
    # 今回の鍵で開けられる宝箱の集合s
    s = keys[i][1]
    c = keys[i][0]
    for j in range(1<<N):
        # 今回の鍵を買わない遷移
        dp[(i+1)%2][j] = min(dp[(i+1)%2][j], dp[i%2][j])
        if dp[i%2][j] != INF:
            m = j | s
            # 買う遷移：遷移元の開けられる宝箱の集合j | 今回の鍵で開けられる宝箱の集合s
            dp[(i+1)%2][m] = min(dp[(i+1)%2][m], dp[i%2][j]+c)
ans = dp[M%2][-1]

if ans != INF:
    print(ans)
else:
    print(-1)


Measured memory_bytes: 49884
#include <bits/stdc++.h>
using namespace std;

int main() {
	int H,W;
	cin >> H >> W;
	string map[H];
	for(int i=0; i<H; i++) cin >> map[i];

	vector<bool> row(H,false), col(W,false);

	for(int i=0; i<H; i++)
		for(int j=0; j<W; j++)
			if(map[i][j]=='#') {
				row[i] = true;
				col[j] = true;
			}

	for(int i=0; i<H; i++) {
		if(row[i]) {
			for(int j=0; j<W; j++) {
				if(col[j])
					cout << map[i][j];
			}
		cout << endl;
		}
	}
}


Measured memory_bytes: 256
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def main():
    N = in_n()
    a = list(in_nn())

    s = a[0]
    for i in range(1, N):
        s = s ^ a[i]

    ans = [0] * N
    for i in range(N):
        ans[i] = a[i] ^ s

    print(' '.join(map(str, ans)))


if __name__ == '__main__':
    main()


Measured memory_bytes: 42416
#include <bits/stdc++.h>
using namespace std;typedef long long ll;typedef vector<ll> vl;typedef vector<vl> vvl;typedef pair<ll,ll> pl;typedef vector<pl> vp;const ll INF=1001001001;const ll LINF=1001001001001001001;const ll D4[]={0,1,0,-1,0};const ll D8[]={0,1,1,0,-1,-1,1,-1,0};template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}
#define fore(i,a,b) for(ll i=(ll)(a);i<=(ll)(b);++i)
#define rep(i,n) fore(i,0,(n)-1)
#define all(x) (x).begin(),(x).end()

void solve(long long K, long long N, std::vector<long long> A){
    ll ma=A[0]+K-A[N-1];
    rep(i,N-1){
        chmax(ma,A[i+1]-A[i]);
    }
    cout<<K-ma<<endl;
}

int main(){
    long long K;
    scanf("%lld",&K);
    long long N;
    scanf("%lld",&N);
    std::vector<long long> A(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&A[i]);
    }
    solve(K, N, std::move(A));
}


Measured memory_bytes: 1792
#include<stdio.h>
#include<iostream>
#include<fstream>
#include<string>
#include<math.h>
#include <set>
#include <list>
using namespace std;

enum command {
	unite = 0,
	same = 1
};
void set_print(const char* msg, const set<int> &s)
{
	cout << msg;
	cout << " " << s.size() << " [";
	const char * delim = "";
	for (set<int>::iterator it = s.begin(); it != s.end(); ++it)
	{
		int c = *it;
		cout << delim << (int)c;
		delim = ",";
	}
	cout << " ]" << endl;
}
int main(){
		std::istream & c_in = cin;
	int n, q;
	c_in >> n >> q;
	typedef list< set<int> > SETS;
	SETS sets;
	for (int i = 0; i < n; ++i)
	{
		set<int> s;
		s.insert(i);
		sets.push_back(s);
	}

	for (int i = 0; i < q; ++i)
	{
		int com, x, y;
		c_in >> com >> x >> y;
		if (com == unite)
		{
			//unite(x,y): x ??????????????? Sx ??¨ y ??????????????? Sy ??????????????????
			SETS::iterator sx = sets.end(), sy = sets.end();
			for (SETS::iterator it = sets.begin(); it != sets.end() && (sx == sets.end() || sy == sets.end()); ++it)
			{
				if (it->find(x) != it->end())
				{
					sx = it;
				}
				if (it->find(y) != it->end())
				{
					sy = it;
				}
			}
			if (sx != sy)
			{
				sx->insert(sy->begin(), sy->end());
				//{
				//	set_print("sx=", *sx);
				//	set_print("sy=", *sy);
				//}
				sets.remove(*sy);
			}
		}
		else if (com == same)
		{
			for (SETS::iterator it = sets.begin(); it != sets.end(); ++it)
			{
				bool notfindx = it->find(x) == it->end();
				bool notfindy = it->find(y) == it->end();

				if (notfindx && notfindy)
				{
					continue;
				}
				int v = (!notfindx) && (!notfindy) ? 1 : 0;
				cout << v << endl;
				break;
			}

		}
	}
}

Measured memory_bytes: 2512
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
typedef pair<int,int> ii;
typedef tree<ii,null_type,less<ii>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	int n; cin>>n;
	double ct=n/2;
	if (n%2) ct++;
	cout<<setprecision(10)<<fixed<<(ct/n)<<endl;
	return 0;
}


Measured memory_bytes: 3728
import java.util.Scanner;

public class Main {
	    public static void main(String[] args) throws Exception {
	        Scanner sc = new Scanner(System.in);
	        String str = sc.next();
	        StringBuffer strBuf = new StringBuffer(str);
	        int q = sc.nextInt();
	        for(int i = 0; i < q; i++){
	            String order = sc.next();
	            int x = sc.nextInt();
	            int y = sc.nextInt()+1;
	            //System.out.println("Abc=" +x +":" + y);
	            //???????????????????????????
	            if(order.equals("replace")){
	            	//????????????????????????????????????
	                String repStr = sc.next();
	                //????????????a???????????????????????????repStr?????????
	                strBuf = strBuf.replace(x,y,repStr);
	                //????????????
	               // System.out.print("strBUF=" + strBuf);
	               //?????????????????¢?????????
	            }else if(order.equals("reverse")){
	            	//????????????a???????????????????????????????????????????????????word?????????
	            	String word = strBuf.substring(x,y);
	            	//a??????b?????????????????\??£????????????
	            	//System.out.print("WORD="+word );
	            	//StringBuffer revBuf = new StringBuffer(strBuf.substring(x,y));
	            	//??°??????StringBuffer?????????
	                StringBuffer revBuf = new StringBuffer(word);
	                //rebuf?????????????????¢?????????????????¨???string?????????
	                String revStr = revBuf.reverse().toString();
	               // System.out.println(revStr);
	                //strBuf??????????????????
	                strBuf = strBuf.replace(x,y,revStr);
	            }else{
	                System.out.println(strBuf.substring(x,y));
	            }
	        }
    }
}

Measured memory_bytes: 29328
#include<iostream>
using namespace std;
int main()
{
	string s;
	cin>>s;
	if(s=="SSS")
		cout<<"0\n";
	else if(s=="RRR")
		cout<<"3\n";
	else if(s=="SRS" || s[1]=='S')
		cout<<"1\n";
	else
		cout<<"2\n";
}

Measured memory_bytes: 3624
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int A[][] = new int[2][N];
    int S1[] = new int[N+1];
    int S2[] = new int[N+1];
    S1[0]=0;
    S2[0]=0;
    for(int i=0;i<=1;i++){
      for(int j=0;j<N;j++){
        A[i][j]=sc.nextInt();        
      }
    }
    for(int i=1;i<=N;i++){
      S1[i]=S1[i-1]+A[0][i-1];
    }
    for(int i=1;i<=N;i++){
      S2[i]=S2[i-1]+A[1][i-1];
    }
    int ans=0;
    for(int i=1;i<=N;i++){
      ans=Math.max(ans,S1[i]+S2[N]-S2[i-1]);
    }
    System.out.println(ans);
  }

  
}


Measured memory_bytes: 22736
#include <stdio.h>
int main(void){
    int H,W,i,j,k;
    scanf("%d%d",&H,&W);
    char c[101];
    for(i=0;i<H;i++){
        scanf("%s",c);
        for(j=0;j<2;j++){
            for(k=0;k<W;k++){
                printf("%c",c[k]);
            }
            printf("\n");
        }
    }
    
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
 
typedef long long int ll;
typedef long double ld;

string s;
ll k;
ll n;

ll dp[105][105][2];

ll solve(ll id,ll num,ll flg)
{
	//cout<<id<<" "<<num<<" "<<flg<<endl;
	if(id==n)
	{
		if(num==k)return 1;
		return 0;
	}
	
	if(dp[id][num][flg]==-1)
	{
		ll cur = 0;
		ll ed = s[id]-'0';
		if(flg)ed=9;
		for(ll i=0;i<=ed;i++)
		{
			
				if(flg)
				{
					if(i==0)
						cur += solve(id+1,num,flg);
					else
						cur += solve(id+1,num+1,flg);
				}
				else
				{
					if(i==ed)
					{
						if(i==0)
							cur += solve(id+1,num,flg);
						else
							cur += solve(id+1,num+1,flg);
					}
					else
					{	
						if(i==0)
							cur += solve(id+1,num,1);
						else
							cur += solve(id+1,num+1,1);
					}
				}
			
		}
		
		dp[id][num][flg] = cur;
		
	}
	return dp[id][num][flg];
	
}

int main()
{
    std::ios_base::sync_with_stdio(0);	
    cin.tie(0);
    cout.tie(0);
    
    cin>>s>>k;
   // cout<<s<<" "<<k<<endl;
    n = s.size();
   //  cout<<n<<endl;
    memset(dp,-1,sizeof(dp));
    
    cout<<solve(0,0,0);
    
    
}


Measured memory_bytes: 384
/*
    -ensure correct output format
    -ensure printing required output
    -reread the problem statement
  */

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>pll;
typedef pair<ll,pair<ll,ll>>plll;
#define fastread() (ios_base:: sync_with_stdio(false),cin.tie(NULL));
#define vll(v) v.begin(),v.end()
#define all(x) x.rbegin(),x.rend()
#define min3(a, b, c)   min(a, min(b, c))
#define max3(a, b, c)   max(a, max(b, c))
#define F first
#define S second
#define in  freopen("input.txt", "r", stdin)
#define out  freopen("output.txt", "w", stdout)
#define minheap int,vector<int>,greater<int>
#define pb push_back
#define eb emplace_back
#define ischar(x)  (('a' <= x && x <= 'z') || ('A' <= x && x <= 'Z'))
#define isvowel(ch) ((ch=='a'||ch=='e'||ch=='i'||ch=='o'||ch=='u')||(ch=='A'|| ch=='E' || ch=='I'|| ch=='O'|| ch=='U'))
#define bug cout<<"BUG"<<endl;
const int Max = 1e6 + 10;
const int Mod = 1e9 + 7;
const double PI  =3.141592653589793238463;
bool compare(const pair<ll,ll> &a, const pair<ll,ll> &b)
{
       return (a.first > b.first);
}
ll lcm(ll a,ll b)
{
    if(a==0 || b==0)return 0;

    return a/__gcd(a,b)*b;
}

void input(ll ara[],ll n)
{
    for(ll i=0; i<n; i++)cin>>ara[i];
}



ll mp[Max+10];

int main()
{

   fastread();

   ll i,j,n,m,p,a,sum=0,k,t,b,c,d,cnt=0,q,l,r,x;

      bool flag=false;

      string str;


        cin>>n;

        ll ara[n+2];

        for(i=0; i<n; i++)
        {
            cin>>ara[i];
        }

        sort(ara,ara+n);

        for(i=0; i<n; i++)
        {
            if(mp[ara[i]]==0)
            {
                for(j=ara[i]; j<=Max; j+=ara[i])
                {
                    mp[j]=1;
                }

                j=i;

                ll cp=0;

                while(i<n && ara[i]==ara[j])i++,cp++;

                if(cp>1)cp=0;

                cnt+=cp;


                i--;
            }
        }

        cout<<cnt<<endl;




}



Measured memory_bytes: 12952
// Problem : C - A x B + C
// Contest : AtCoder - AtCoder Beginner Contest 179
// URL : https://atcoder.jp/contests/abc179/tasks/abc179_c
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

// $%U%$
// Mere bas ka nahi hai
// still i'm trying
// apna time aayega
//
//        .--------------.  
//        | Try First One|
//        '--------------'
//                |     .--------------.
//                |     |              |
//                V     V              |
//              .--------------.       |
//              |      AC.     |<---.  |  
//              '--------------'    |  |
//              (True)|  |(False)   |  |
//           .--------'  |          |  |
//           |           V          |  |
//           |  .--------------.    |  |
//           |  |   Try Again  |----'  |
//           |  '--------------'       |
//           |                         |
//           |  .--------------.       |
//           '->| Try Next One |-------'
//              '--------------'                          		  
//
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll power(ll x,ll y,ll m){if(y==0)return 1;ll p=power(x,y/2,m)%m;p=(p*p)%m;return (y%2==0)?p:(x*p)%m;}
ll nCr(ll n,ll r,ll m){if(r>n)return 0;ll a=1,b=1,i;for(i=0;i<r;i++){a=(a*n)%m;--n;}while(r){b=(b*r)%m;--r;}return (a*power(b,m-2,m))%m;}
#define Test int t;cin>>t;while(t--)
#define endl '\n'
void solve()
{
	ll n;
	cin >> n;
	vector<ll> v(n+1);
	ll ans=0;
	for(ll i=1;i<=n;++i)
	{
		ans+=(n%i==0?n/i-1:(n/i));
	}
	cout << ans << endl;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	//Test
	solve();
	return 0;
}


Measured memory_bytes: 11112