akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;;
#define ll long long
#define rep(i, n) for(int i = 0;i < n;i++)
#define repr(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define INF 1<<30
#define LINF 1LL<<62
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define pb push_back
const int MOD = 1000000007;
 
typedef pair<ll, ll> P;
typedef pair<ll, P> PP;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n,k; cin >> n >> k;
  if(k>(n-1)*(n-2)/2){
      cout << -1 << endl;
  }else{
      cout << n*(n-1)/2 - k<< endl;
      FOR(i,2,n+1){
          cout << 1 << " " <<  i << endl;
      }
      ll num = (n-1)*(n-2)/2 -k;
      ll from = 2;
      ll to = 3;
      while(num){
          cout << from << " " << to << endl;
          if(to<n)to++;
          else {
              from++;
              to = from +1;
          }
          num--;
      }
  }
}

Measured memory_bytes: 256
#include<iostream>
#include<cstring>
using namespace std;
int tx,ty,ax[4005],ay[4005],dp[4005][16005];
void dfsx(int s,int n){
	if(dp[s][n+8000])
		return;
	if(s<tx){
		dfsx(s+1,n-ax[s]);
		dfsx(s+1,n+ax[s]);
	}
	dp[s][n+8000]=1;
}
void dfsy(int s,int n){
	if(dp[s][n+8000])
		return;
	if(s<ty){
		dfsy(s+1,n-ay[s]);
		dfsy(s+1,n+ay[s]);
	}
	dp[s][n+8000]=1;
}
int main(){
	string s;
	int x,y;
	cin>>s>>x>>y;
	int n=s.size(),fx=1;
	for(int i=0;i<n;i++){
		if(s[i]=='F'){
			if(fx)
				ax[tx]++;
			else
				ay[ty]++;
		}
		else{
			if(fx)
				fx=0,tx++;
			else
				fx=1,ty++;
		}
	}
	if(s[n-1]=='F'){
		if(fx)
			tx++;
		else
			ty++;
	}
	dfsx(1,ax[0]);
	int bx=dp[tx][8000+x];
	memset(dp,0,sizeof(dp));
	dfsy(0,0);
	int by=dp[ty][8000+y];
	if(bx&&by)
		cout<<"Yes"<<endl;
	else
		cout<<"No"<<endl;
	return 0;
}

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

const long double PI = acos(-1);
constexpr long double EPS = 1e-15;
constexpr int inf = 2e9;
constexpr ll INF = 2e18;
constexpr ll MOD = 1e9+7;
constexpr ll MOD1 = 998244353;
typedef pair<ll,ll> P;

//#define all(v) (v).begin(), (v).end()
#define rep(i,a,b) for (int i = (a); i < (b); i++)
#define REP(i,n) rep(i,0,n)
#define sz(s) (s).size()
#define pb push_back
#define fi first
#define se second
//#define mp make_pair


void solve() {
  int a,b,c;
  cin >> a >> b >> c;
  cout << (a + b + c - max({a,b,c})) << endl;
}

int main(int argc, char *argv[]){

  /*Regular*/
  int case_num = 1;
  if (argc > 1 && stoi(argv[1])) cin >> case_num;
  REP(case_no, case_num) {
    cerr << endl << "case " << case_no + 1 << endl;
    solve();
  }

  // /*ICPC*/
  // while (cin >> t >> d >> l, t) {
  //   solve();
  // }

  //solve();
  return 0;
}

Measured memory_bytes: 256
import numpy as np


def main():
    N, K = list(map(int, input().split()))
    H = np.array(list(map(int, input().split())))

    INF = float('inf')

    dp = np.array([INF for _ in range(N)])
    dp[0] = 0

    for i in range(1, N):
        max_dist = min(K, i)
        dp[i] = np.min(dp[i - max_dist:i] + np.abs(H[i] - H[i - max_dist:i]))

    print(int(dp[-1]))


if __name__ == '__main__':
    main()


Measured memory_bytes: 22840
from sys import stdin
H, W = [int(_) for _ in stdin.readline().rstrip().split()]
S = [stdin.readline().rstrip() for _ in range(H)]

left = [[0]*W for i in range(H)]
right = [[0]*W for i in range(H)]
up = [[0]*W for i in range(H)]
down = [[0]*W for i in range(H)]

for i in range(H):
    p = 0
    for j in range(W):
        if S[i][j] == '#':
            p = 0
        else:
            p += 1
        left[i][j] = p
for i in range(H):
    p = 0
    for j in range(W)[::-1]:
        if S[i][j] == '#':
            p = 0
        else:
            p += 1
        right[i][j] = p
for j in range(W):
    p = 0
    for i in range(H):
        if S[i][j] == '#':
            p = 0
        else:
            p += 1
        up[i][j] = p
for j in range(W):
    p = 0
    for i in range(H)[::-1]:
        if S[i][j] == '#':
            p = 0
        else:
            p += 1
        down[i][j] = p

ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        ans = max(ans, left[i][j] + right[i][j] + up[i][j] + down[i][j] - 3) 

print(ans)

Measured memory_bytes: 177672
from itertools import permutations
from math import factorial

N = int(input())
co = [tuple(map(int, input().split())) for _ in range(N)]
total = 0
for path in permutations(range(N)):
    for i, j in zip(path[0:N - 1], path[1:]):
        total += ((co[i][0] - co[j][0]) ** 2 + (co[i][1] - co[j][1]) ** 2) ** 0.5
print(total / factorial(N))


Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

int main(){
  int n, k;
  cin >> n >> k;
  vector<int> backet(n,0);
  set<int> s;
  for(int i=0; i<n; i++){
    int temp;
    cin >> temp;
    backet[temp - 1] += 1;
    s.insert(temp);
  }

  sort(backet.begin(), backet.end());

  int ans = 0;
  for(int i=0; i<n; i++){
    if(backet.at(i) == 0){

    }else{
      ans += backet.at(i);
      s.erase(s.begin());
    }
    if(k >= s.size()){
      break;
    }
  }

  cout << ans;
  return 0;
}


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

int main(){
  string S; cin >> S;
  int N = S.size();
  int begin, end;
  
  for(int i = 0; i < N; i++){
    if(S[i] == 'A'){
      begin = i;
      break;
    }
  }
  for(int i = N-1; i >= 0; i--){
    if(S[i] == 'Z'){
      end = i;
      break;
    }
  }
  
  cout << end - begin + 1 << endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define FOR(I,X,Y) for(int (I)=(X);(I)<(Y);(I)++)
#define REP(I,X,Y) for(int (I)=(Y)-1;(I)>=(X);(I)--)
#define ALL(X) (X).begin(),(X).end()
#define INF 1000000007
#define LINF 1000000000000000007
typedef long long ll;
using namespace std;


//データ数 < 2^(log2n)
constexpr ll log2n = 20;
constexpr ll sizeofn = 1 << log2n+1;
ll SegmentTree[sizeofn];
ll STconvert(ll i,ll j){
  return (1<<log2n)/(j-i+1) + i/(j-i+1);
}

ll STmerge(ll i,ll j,ll k,ll l){
  return min(SegmentTree[STconvert(i,j)],SegmentTree[STconvert(k,l)]);
}

ll STquery(ll i,ll j){
  if(i > j)swap(i,j);
  REP(rep,0,log2n+1){
    ll p = 1 << rep;
    if(i%p == 0 && i+p-1 < j){
      return min(STquery(i+p,j),SegmentTree[STconvert(i,i+p-1)]);
    }
    else if(i%p == 0 && i+p-1 <= j){
      return SegmentTree[STconvert(i,j)];
    }
  }
}

void STchange(ll i,ll j){
  SegmentTree[STconvert(i,i)] = j;
  FOR(rep,1,log2n+1){
    ll p = 1 << rep;
    SegmentTree[STconvert(i/p*p,i/p*p+p-1)] = STmerge(i/p*p,i/p*p+p/2-1,i/p*p+p/2,i/p*p+p-1);
  }
}

int main(){
  vector<ll> ans;
  ll n,q,com,x,y,inf=((ll)1<<31)-1;
  cin >> n >> q;
  FOR(i,0,n)STchange(i,inf);
  FOR(i,0,q){
    cin >> com >> x >> y;
    if(com)ans.push_back(STquery(x,y));
    else STchange(x,y);
  }
  for(auto x:ans)cout << x << endl;
}



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

int main(){
    int K;
    string S,moji;
    cin >> K >> S;

    if(S.size() <= K)
        cout << S << endl;
    else{
        for(int i = 0;i < K;i++)
            cout << S.at(i);
        cout << "..." << endl;

    }
}

Measured memory_bytes: 3632
#include<iostream>
#include<vector>
#include <cmath>
#include <map>
#include <algorithm>
#include <string>
using namespace std;
typedef long long int ll;
int main(void){
    ll i,j;
    int n;
    cin >> n;
    int bit;
    vector<int> a(n);
    vector<vector<int>> x(n);
    vector<vector<int>> y(n);
    for(i = 0;i < n;++i){
        cin >> a.at(i);
        for(j = 0;j < a.at(i);++j){
            int tx,ty;
            cin >> tx >> ty;
            --tx;
            x.at(i).push_back(tx);
            y.at(i).push_back(ty);
        }
    }
    int ans = 0;
    for(bit = 0;bit < (1 << n);++bit){
        int tmp = 0;
        vector<int> syouziki(n,0);
        for(i = 0;i < n;++i){
            if(bit & (1 << i)){
                ++tmp;
                syouziki.at(i) = 1;
            }
        }
        if(tmp <= ans){
            continue;
        }
        bool flag = true;
        for(i = 0;i < n;++i){
            if(!syouziki.at(i)){
                continue;
            }
            for(j = 0;j < a.at(i);++j){
                int hito = x.at(i).at(j);
                if(syouziki.at(hito) != y.at(i).at(j)){
                    flag = false;
                    break;
                }
            }
            if(!flag){
                break;
            }
        }
        if(flag){
            ans = tmp;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
using namespace std;
int main(){
  string str;
  int alp[26]={};
  while(getline(cin,str)){
    for(int i=0,l=str.size();i<l;i++){
      if(str[i]>='a'&&str[i]<='z') alp[str[i]-'a']++;
      else  if(str[i]>='A'&&str[i]<='Z') alp[str[i]-'A']++;
    }
  }
  for(int i=0;i<26;i++){
    printf("%c : %d\n",i+'a',alp[i]);
  }
}


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

int main(){

  int n;
  string a, b, c;
  int cnt = 0;

  cin >> n >> a >> b >> c;
  for(int i=0;i<n;i++){
    if(a[i] == b[i] && a[i] == c[i] && b[i] == c[i]);
    if(a[i] != b[i] && a[i] != c[i] && b[i] == c[i]) cnt++;
    if(a[i] != b[i] && a[i] == c[i] && b[i] != c[i]) cnt++;
    if(a[i] == b[i] && a[i] != c[i] && b[i] != c[i]) cnt++;
    if(a[i] != b[i] && a[i] != c[i] && b[i] != c[i]) cnt+=2;
  }

  cout << cnt << endl;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());

		long c[] = new long[n];

		String str[] = br.readLine().split(" ");

		for (int i = 0; i < n; i++) {
			long a = Long.parseLong(str[i]);
			c[i] = a - (i + 1);
		}

		Arrays.sort(c);
		long b = c[n / 2];

		long ans = 0;

		for (int i = 0; i < n; i++) {
			ans += Math.max(b - c[i], -b + c[i]);
		}

		System.out.println(ans);
	}

}

Measured memory_bytes: 63384
import java.util.*;
public class Main {
    static double[][] nums;
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        nums=new double[n][2];
        nums[0][0]=sc.nextDouble();
        nums[0][1]=(10.0-sc.nextDouble())/10.0;
        for(int i=1;i<n;i++){
            nums[i][0]=sc.nextInt();
            nums[i][1]=nums[i-1][1]*(10-sc.nextInt())/10.0;
        }
        int q=sc.nextInt();
        int li;
        int ri;
        for(int i=0;i<q;i++){
            li=sc.nextInt();
            ri=sc.nextInt();
            System.out.println((double)((nibu(ri)==-1?1:nums[nibu(ri)][1])/(nibu(li)==-1?1:nums[nibu(li)][1])*1000000000));
        }
    }
    static int nibu(int q){//にぶたんでnums[i][1]<q<nums[i+1][1]になるiを見つける
        int ans=nums.length/2;
        int toadd=nums.length/2;
        while(true){
            if(nums[ans][0]<q){
                ans+=Math.max(1, toadd/=2);
            }else{
                ans-=Math.max(1, toadd/=2);
            }
            if(ans<0||ans>=nums.length-1||(nums[ans][0]<q&&nums[ans+1][0]>q))break;
        }
        return ans;
    }
    
}


Measured memory_bytes: 149560
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict

INF = float("inf")

def getlist():
	return list(map(int, input().split()))

def warshall_floyd(d, n):
	for k in range(n):
		for i in range(n):
			for j in range(n):
				d[i][j] = min(d[i][j],d[i][k] + d[k][j])
	return d


#処理内容
def main():
	N, M, L = getlist()
	d = [[float("inf") for i in range(N)] for i in range(N)]
	for i in range(M):
		a, b, w = getlist()
		d[a - 1][b - 1] = w
		d[b - 1][a - 1] = w

	for i in range(N):
		d[i][i] = 0

	d = warshall_floyd(d, N)
	d2 = [[float("inf") for i in range(N)] for i in range(N)]
	for i in range(N):
		for j in range(N):
			if d[i][j] <= L:
				d2[i][j] = 1
	for i in range(N):
		d2[i][i] = 0

	d2 = warshall_floyd(d2, N)

	Q = int(input())
	for i in range(Q):
		s, t = getlist()
		if d2[s - 1][t - 1] == INF:
			print(-1)
		else:
			print(d2[s - 1][t - 1] - 1)



if __name__ == '__main__':
	main()

Measured memory_bytes: 126428
main :: IO ()
main = do
    n <- readLn
    let s = solve n
    putStrLn s

solve i = show a ++ ":" ++ show b ++ ":" ++ show c
    where
      a = (i `div` 60) `div` 60
      b = (i `div` 60) `mod` 60
      c =  i `mod` 60


Measured memory_bytes: 3600
def resolve():
    import math as m
    from collections import defaultdict
    N = int(input())
    A = [int(i) for i in input().split()]
    preSum = [0] * (N + 1)
    dd = defaultdict(int)
    dd[0] = 1
    for i in range(N):
        preSum[i + 1] = preSum[i] + A[i]
        dd[preSum[i] + A[i]] += 1
    sumA = 0
    for key in dd.keys():
        if dd[key] > 1:
            sumA += m.factorial(dd[key]) // (m.factorial(dd[key] - 2) * 2)
    print(sumA)


resolve()


Measured memory_bytes: 46876
n=int(input())
s=input()
w=[0]*(n+1)
b=[0]*(n+1)
for i in range(1,n+1):
  w[i]=w[i-1]+1 if s[i-1]=="#" else w[i-1]
  b[-i-1]=b[-i]+1 if s[-i]=="." else b[-i]
print(min([x+y for x,y in zip(w,b)]))

Measured memory_bytes: 20976
#include<iostream>
#include <string>
using namespace std ;

int main(){
	string s ; cin >> s ;
	int cnt = 0 ;
	for(int i=0;i<s.size();i++){
		if(i%2==0){
			if(s.at(i)=='p') cnt-- ;
		}else{
			if(s.at(i)=='g') cnt++ ;
		}
	}
	cout << cnt << endl ;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#include <stdlib.h>
#include <iostream>
#include <string>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;

int main()
{
   int n;
   cin >> n;
   int a ;
   cin >> a;
   int ans = n*n -a;
   cout << ans << endl;
}


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

// Shrotening
#define fst first
#define snd second
#define pb push_back

// Loop
#define FOR(i,a,b) for(long i=(a);i<(b);++i)
#define RFOR(i,a,b) for(long i=(a);i>=(b);--i)

#define REP(i,a) for(long i=0;i<(a);++i)
#define RREP(i,a) for(long i=(a);i>=0;--i)

#define EACH(i,a) for(auto (i)=(a).begin(),_END=(a).end();i!=_END;++i)
#define REACH(i,a) for(auto (i)=(a).rbegin(),_END=(a).rend();i!=_END;++i)

//Algorithm
#define ALL(a) (a).begin(), a.end()
#define RALL(a) (a).rbegin(), a.rend()
#define EXIST(a,x) ((a).find(x)!=(a).end())
#define SORT(a) std::sort((a).begin(), (a).end())
#define UNIQUE(a) std::sort((a).begin(), a.end()), a.erase(std::unique((a).begin(), a.end()), a.end());
#define SUM(a) std::accumulate((a).begin(), (a).end(), 0);

//Setting
#define OPT std::cin.tie(0);std::ios::sync_with_stdio(false);

//debug message
bool debug = true;
#define MSG(s)   if(debug){std::cout << s << std::endl;}
#define DEBUG(x) if(debug){std::cout << "debug(" << #x << "): " << x << std::endl;}

//alias
typedef long long LL;
typedef std::vector<char> VC;
typedef std::vector<int>  VI;
typedef std::vector<long> VL;
typedef std::vector<long long> VLL;

typedef std::vector< VC > VC2;
typedef std::vector< VI > VI2;
typedef std::vector< VL > VL2;
typedef std::vector< VLL > VLL2;

typedef std::pair<int,int> PII;

VC2 C;
int main() {
    C.resize(3, VC(3));
    REP(i, 2){
        REP(j, 3) {
            std::cin >> C[i][j];
        }
    }
    if(C[0][0] == C[1][2] && C[0][1] == C[1][1] && C[0][2] == C[1][0]) {
        std::cout << "YES" << std::endl;
    }else{
        std::cout << "NO" << std::endl;
    }
}

Measured memory_bytes: 764
#include<iostream>
using namespace std;
int main(){
  int N;
  cin >> N;
  if(N % 1110 < 10 || (N % 1000) % 111 == 0){
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll          long long int
#define lld          long double
#define pb          push_back
#define pii         pair<ll,ll>
#define mi          map<ll,ll>
#define vec         vector<ll>
#define all(a)     (a).begin(),(a).end()
#define F           first
#define S           second
#define mod         10000000000007
#define rep(i,a,b)	for(ll  i=a;i<b;i++)
#define repi(i,a,b)	for(ll  i=a;i<=b;i++)
#define per(i,a,b)  for(ll i=a;i>=b;i--)
#define mp          make_pair
#define mit         map<ll,ll>::iterator
#define sit         set<ll>::iterator
#define xxx         exit(0);
#define pit         pair<ll,ll>::iterator
#define tr(container, it) for(__typeof(container.begin()) it = container.begin(); it != container.end(); it++)
using namespace std;
ll a[405], dp[405][405], n;
ll sum(ll i, ll j)
{
	ll d=0;
	repi(k,i,j) d+=a[k];
	return d;
}
ll cc(ll s, ll e)
{
	if(s==e) dp[s][e] = 0;
	if(s>e) return mod;
	if(dp[s][e] != -1 )return dp[s][e];
	ll ans = mod, x, cost;
	
	repi(i,s,e-1)
	{
		ans = min(ans, cc(s,i) + cc(i+1,e) + sum(s,e));
	}
	return dp[s][e]=ans;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int TESTS=1;
//	cin>>TESTS;
    while(TESTS--)
    {
    	ll i,j,k,l,m,h,w,val,K;
    	cin>>n;
    	rep(i,0,n) cin>>a[i];
    	repi(i,0,n){
    		repi(j,0,n) dp[i][j]=-1;
		}
    	cout<<cc(0,n-1);
	}
	return 0;
}

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

int main()
{
	int x, y;
	cin >> x >> y;
	
	for (int i = 0; i <= 100; ++i)
	{
		for (int j = 0; j <= 100; ++j)
		{
			if ((i + j == x) and (2 * i + 4 * j == y))
			{
				cout << "Yes" << endl;
				return 0;
			}
		}
	}
	
	cout << "No" << endl;
	
	return 0;
}


Measured memory_bytes: 3592
#include<iostream>
#include<string>

using namespace std;

int main(void) {
    int a[3];
    int b[3];
    int c[4][4];
    for(int i =0; i < 3; i++)
        for(int j =0; j < 3; j++) {
            cin >> c[i][j];
        }
    b[0] = c[0][0];
    b[1] = c[0][1];
    b[2] = c[0][2];
    a[0] = c[0][0] - b[0];
    a[1] = c[1][0] - b[0];
    a[2] = c[2][0] - b[0];
    // for(int i =0; i < 3; i++) {
    //     if (a[i] < 0 || b[i] < 0 || a[i] > 100 || b[i] > 100) {
    //         cout << "No" << endl;
    //         return 0;
    //     }
    // }
    for(int i =0; i < 3; i++)
        for(int j = 0; j < 3; j++) {
            if (c[i][j] != a[i] + b[j]) {
                cout << "No" << endl;
                return 0;
            }
        }

    cout << "Yes" << endl;
}


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

void display(int a[], int n);

int main() {
    int num;
    cin >> num;

    int a[num];
    for ( int i = 0; i < num; i++ ) cin >> a[i];

    display(a, num);

    for ( int i = 1; i < num; i++ ) {
        int j = i - 1;
        int key = a[i];

        while ( j >= 0 && a[j] > key ) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;

        display(a, num);
    }
}

void display(int a[], int n) {
    for ( int i = 0; i < n - 1; i++ ) {
        cout << a[i] << " ";
    }
    cout << a[n-1] << endl;
}


Measured memory_bytes: 3084
import sys
from collections import deque

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

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


class Dinic:
    def __init__(self, N):
        self.N = N
        self.G = [[] for i in range(N)]

    def add_edge(self, fr, to, cap):
        forward = [to, cap, None]
        forward[2] = backward = [fr, 0, forward]
        self.G[fr].append(forward)
        self.G[to].append(backward)

    def add_multi_edge(self, v1, v2, cap1, cap2):
        edge1 = [v2, cap1, None]
        edge1[2] = edge2 = [v1, cap2, edge1]
        self.G[v1].append(edge1)
        self.G[v2].append(edge2)

    def bfs(self, s, t):
        self.level = level = [None] * self.N
        deq = deque([s])
        level[s] = 0
        G = self.G
        while deq:
            v = deq.popleft()
            lv = level[v] + 1
            for w, cap, _ in G[v]:
                if cap and level[w] is None:
                    level[w] = lv
                    deq.append(w)
        return level[t] is not None

    def dfs(self, v, t, f):
        if v == t:
            return f
        level = self.level
        for e in self.it[v]:
            w, cap, rev = e
            if cap and level[v] < level[w]:
                d = self.dfs(w, t, min(f, cap))
                if d:
                    e[1] -= d
                    rev[1] += d
                    return d
        return 0

    def flow(self, s, t):
        flow = 0
        INF = 10**9 + 7
        G = self.G
        while self.bfs(s, t):
            *self.it, = map(iter, self.G)
            f = INF
            while f:
                f = self.dfs(s, t, INF)
                flow += f
        return flow


def main():
    N = in_n()
    ab = [tuple(in_nn()) for _ in range(N)]
    cd = [tuple(in_nn()) for _ in range(N)]

    start = 0
    goal = 2 * N + 1
    dinic = Dinic(goal + 1)
    for i in range(1, N + 1):
        dinic.add_edge(start, i, 1)
    for i in range(N + 1, 2 * N + 1):
        dinic.add_edge(i, goal, 1)

    for i in range(N):
        for j in range(N):
            a, b = ab[i]
            c, d = cd[j]
            if a < c and b < d:
                dinic.add_edge(1 + i, N + 1 + j, 1)

    ans = dinic.flow(start, goal)
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 9948
#include <bits/stdc++.h>
    using namespace std;
 
    #define fast ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
    #define mod 1000000007
    #define qmod 998244353
    #define M 1000001
    #define endl "\n"
    #define all(a) (a).begin(),(a).end()
    #define rep(i,a,b) for(int i=a;i<b;++i)
    #define repr(i,a,b) for(int i=a;i>=b;--i)
    #define F first
    #define S second
    #define pb push_back
    #define mp make_pair
 
    typedef long long ll;
    typedef pair<int,int> pii;
    typedef vector<int> vi;
    typedef vector<string> vs;
    typedef vector<pii> vii;
    typedef vector<vi> vvi; 

    int main(){
                
   /* #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin); 
    freopen("output.txt","w",stdout);   
    #endif */
 
        fast;
        int t=1;
        // cin>>t;  
        while(t--){     
            int n;
            cin>>n;
            int ans[n+1]={};
            rep(i,1,n){
                int t;
                cin>>t;
                ans[t]++;
            }
            rep(i,1,n+1) cout<<ans[i]<<endl;
        } 
        return 0;  
    }       


    //keep it simple stupid 

Measured memory_bytes: 4348
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <functional>
#include <utility>
#include <queue>
#include <vector>
using namespace std;
typedef long long int ll;
const int MOD = 1000000007;

int main(){
    string o;
    string e;
    cin >> o;
    cin >> e;

    for(int i=0; i< e.size(); i++){
        cout << o[i] << e[i];        
    }
    if(o.size() != e.size()){
        cout << o[o.size() - 1];
    }
    
    return 0;
}

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

#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pb push_back
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mii map<int,int>
#define mll map<ll,ll>
#define all(x) (x).begin(),(x).end()
#define S(x) (int)(x).size()
#define L(x) (int)(x).length()

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int , null_type , less<int> , rb_tree_tag , tree_order_statistics_node_update> ordered_set;

const int mod = 1e9+7;
const ll infl = 0x3f3f3f3f3f3f3f3fLL;
const int infi = 0x3f3f3f3f;

void solve()
{
	int x;
	cin>>x;
	x/=200;
	cout<<10-x<<'\n';
}

int main()
{
	IOS
	int t=1;
	//cin>>t;
	while(t--)
	{
		solve();
	}
}


Measured memory_bytes: 3648
#[allow(unused_imports)]
use std::cmp;

// Input macro from https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
  (source = $s:expr, $($r:tt)*) => {
    let mut iter = $s.split_whitespace();
    input_inner!{iter, $($r)*}
  };
  ($($r:tt)*) => {
    let s = {
      use std::io::Read;
      let mut s = String::new();
      std::io::stdin().read_to_string(&mut s).unwrap();
      s
    };
    let mut iter = s.split_whitespace();
    input_inner!{iter, $($r)*}
  };
}

macro_rules! input_inner {
  ($iter:expr) => {};
  ($iter:expr, ) => {};

  ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
    let $var = read_value!($iter, $t);
    input_inner!{$iter $($r)*}
  };
}

macro_rules! read_value {
  ($iter:expr, ( $($t:tt),* )) => {
    ( $(read_value!($iter, $t)),* )
  };

  ($iter:expr, [ $t:tt ; $len:expr ]) => {
    (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
  };

  ($iter:expr, chars) => {
    read_value!($iter, String).chars().collect::<Vec<char>>()
  };

  ($iter:expr, usize1) => {
    read_value!($iter, usize) - 1
  };

  ($iter:expr, $t:ty) => {
    $iter.next().unwrap().parse::<$t>().expect("Parse error")
  };
}

fn main() {
  input! {
    _n: usize,
    s: chars,
    q: usize,
    query: [usize; q],
  }
  for &k in &query {
    let mut ans = 0i64;
    let mut d = 0;
    let mut m = 0;
    let mut dm = 0;
    for (i, &c) in s.iter().enumerate() {
      if let Some(out) = i.checked_sub(k) {
        match s[out] {
          'D' => {
            d -= 1;
            dm -= m;
          },
          'M' => {
            m -= 1;
          }
          _ => (),
        }
      }
      match c {
        'D' => {
          d += 1;
        },
        'M' => {
          m += 1;
          dm += d;
        },
        'C' => {
          ans += dm;
        },
        _ => (),
      }
    }
    println!("{}", ans);
  }
}


Measured memory_bytes: 13560
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<string>
#include<vector>
#include<map>
using namespace std;
//aからbに向かう,true=右回りfalse=左回り
int get(int a,int b,int n,bool f){
    if(f){
    if(a>b)return b+n-a;
    else return b-a;
    }
    else{
    if(a>b)return a-b;
    else return a+n-b;
    }
}
int main(){
	int n,m,p,t[120000],ans;
	int a=0,b=0;
	cin>>n>>m>>p;
	ans=n;
    	for(int i=0;i<m;i++)cin>>t[i];
   	 sort(t,t+m);
   	 for(int i=0;i<m;i++){
   	 a=max(a,get(p,t[i],n,1));
    	}
   	 for(int i=0;i<m;i++){
   	 b=max(b,get(p,t[i],n,0));
   	 }
    	if(a<b)ans=a;
	else ans=b;

    for(int i=0;i<m;i++){
    ans=min(ans,get(p,t[i],n,true)*2+get(p,t[i+1],n,0));
    if(i==m-1)ans=min(ans,get(p,t[i],n,1)*2+get(p,t[0],n,0));
    }

    for(int i=m-1;i>=0;i--){
    if(i!=0)ans=min(ans,get(p,t[i],n,0)*2+get(p,t[i-1],n,1));
    else ans=min(ans,get(p,t[i],n,0)*2+get(p,t[m-1],n,1));
    }

    if(m==1)cout<<min(get(p,t[0],n,1),get(p,t[0],n,0))*100<<endl;
    else cout<<ans*100<<endl;
    return 0;
}

Measured memory_bytes: 1220
#include <bits/stdc++.h>
#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;
typedef long long ll;
typedef pair<ll, ll> P;
typedef vector<vector<ll>> Matrix;
 
const char wall = '#';
vector<vector<char>> fields;
vector<vector<bool>> used;
vector<vector<ll>> dist;
const int dx[4] = {0, -1, 0, 1};
const int dy[4] = {1, 0, -1, 0};
 
vector<ll> A;
// vectorのリサイズ
// A.resize(N);
 
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a*b/gcd(a, b);}
 
const int MOD = 1000000007;
 
long long fastpow(long long x, long long n) {
    long long ret = 1;
    while (n > 0) {
        if (n & 1) ret = ret * x % MOD;  // n の最下位bitが 1 ならば x^(2^i) をかける
        x = x * x % MOD;
        n >>= 1;  // n を1bit 左にずらす
    }
    return ret;
}
 
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
 
  ll n;
  cin >> n;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];
 
  map<int, int> mp;
  rep(i, n) {
    if (!mp.count(a[i])) mp[a[i]]++;
    else if (mp[a[i]] == 1) mp[a[i]]++;
    else {
      cout << 0 << endl;
      return 0;
    }
  }
  if (mp.count(0) && mp[0] != 1) {
    cout << 0 << endl;
    return 0;
  }
  vector<ll> v;
  for(auto m: mp) {
    if (m.first != 0 && m.second != 2) {
      cout << 0 << endl;
      return 0;
    }
    v.push_back(m.first);
  }
 
  rep(i, v.size()-1) {
    if (v[i+1]-v[i] != 2)  {
      cout << 0 << endl;
      return 0;
    }
  }
  cout << fastpow(2, n/2)<< endl;
  return 0;
}


Measured memory_bytes: 4092
#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <math.h>
#include <algorithm>
using namespace std;

int main() {
  int N;
  cin >> N;
  pair<pair<string, int>, int> X[N];
  for(int i=0; i<N; ++i){
    string city;
    int score;
    cin >> city >> score;
    X[i] = make_pair(make_pair(city, -score), i+1);
  }
  sort(X, X+N);
  
  for(int i=0; i<N; ++i) cout << X[i].second << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int int64_t
#define IOS ios_base::sync_with_stdio(false), cin.tie(0)
#define M 1000000007
#define EPS 1e-9
#define v(x) vector<x>
#define pii pair<int, int>
#define pb push_back
#define fr first
#define se second
#define all(x) x.begin(), x.end()
#define endl "\n"
#define size(x) (int)x.size()
#define debug(x) cout << #x << " = " << x << endl
using namespace std;
//Time complexity : 
//Space complexity : 

int32_t main() {
    IOS;
    #ifndef ONLINE_JUDGE
        freopen("D://Computer Science Material//input.txt", "r", stdin);
        freopen("D://Computer Science Material//output.txt", "w", stdout);
    #endif
    // int t;
    // cin >> t;
    // while(t--) {
        
    // }
    int n, w;
    cin >> n >> w;
    v(pii) items(n);
    for(pii &p : items) 
        cin >> p.fr >> p.se;
    sort(all(items));
    v(v(int)) dp(n + 1, v(int) (w + 1));
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j <= w; j++) {
            if(j < items[i - 1].fr)
                dp[i][j] = dp[i - 1][j];
            else 
                dp[i][j] = max(dp[i - 1][j], items[i - 1].se + dp[i - 1][j - items[i - 1].fr]);
        }
    }
    cout << dp[n][w] << endl;
    return 0;
}   

Measured memory_bytes: 83108
import java.util.*;
public class Main {
    public static void main(String[] args){
 Scanner sc = new Scanner(System.in);
 int N = sc.nextInt();
 int i;
 double pow=1;
 double ans = 1;
 for(i = 1; i <= N; i++){
     pow = pow * i;
  ans = pow %(Math.pow(10.0,9.0)+7.0);
pow = ans;
}
System.out.println((int)ans);
     }
 }


Measured memory_bytes: 21844
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys

X, Y = map(int, input().split())

def score(s):
    if s == 1:
        return 300000
    elif s == 2:
        return 200000
    elif s == 3:
        return 100000
    else:
        return 0

ans = score(X) + score(Y)
if X == Y == 1:
    ans += 400000
print(ans)



Measured memory_bytes: 7976
# -*- coding: utf-8 -*-
N = int(input())
S = input()


import collections, bisect
n_indices_dict = [[] for _ in range(10)]
for i, n in enumerate(S):
    n_indices_dict[int(n)].append(i)

candidates = [(n1, n2, n3)
                for n1 in range(10)
                   for n2 in range(10)
                       for n3 in range(10)]


# print(n_indices_dict)
# exit()

# candidates = [(2, 2, 4)]

ret = 0
for n1, n2, n3 in candidates:
    if n_indices_dict[n1]:
        v1 = n_indices_dict[n1][0]

        if n_indices_dict[n2]:
            i2 = bisect.bisect_right(n_indices_dict[n2], v1)
            if i2 == len(n_indices_dict[n2]):
                continue

            v2 = n_indices_dict[n2][i2]
            if v1 >= v2:
                continue


            if n_indices_dict[n3]:
                i3 = bisect.bisect_right(n_indices_dict[n3], v2)
                if i3 == len(n_indices_dict[n3]):
                    continue

                v3 = n_indices_dict[n3][i3]
                if v2 >= v3:
                    continue

                ret += 1
                # print(v1, v2, v3, n1, n2, n3)


print(ret)



Measured memory_bytes: 40176
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e4 + 10;
int fight[MAXN][MAXN], pv[MAXN];

int main(){
	ios::sync_with_stdio(0);
	cout << setprecision(10) << fixed;
	int n;
	cin >> n;
	for (int i = 1; i <= n; ++i){
		fight[i][0] = 1;
		for (int j = 1; j <= n - 1; ++j){
			cin >> fight[i][j];
		}
	}
	int day = 1;
	while (1){
		bool flag = false;
		for (int i = 1; i <= n; ++i){
			int done = fight[i][0];
			if (done == n || pv[i] == day){
				continue;
			}
			int oppo = fight[i][done];
			int od = fight[oppo][0];
			if (pv[oppo] != day && od < n && fight[oppo][od] == i){
				fight[i][0]++, fight[oppo][0]++;
				pv[i] = pv[oppo] = day;
				flag = true;
			}
		}
		if (!flag){
			break;
		}
		day++;
	}
	for (int i = 1; i <= n; ++i){
		if (fight[i][0] != n){
			cout << -1;
			return 0;
		}
	}
	cout << day - 1;
	return 0;
}



Measured memory_bytes: 39552
A = int(input())
B = int(input())
C = int(input())
X = int(input())
count = 0
for a in range(A+1):
    for b in range(B+1):
        for c in range(C+1):
            if X == 500*a+100*b+50*c:
                count += 1
print(count)


Measured memory_bytes: 2940
macro_rules! input {
     (source = $s:expr, $($r:tt)*) => {
         let mut iter = $s.split_whitespace();
         input_inner!{iter, $($r)*}
     };
     ($($r:tt)*) => {
         let s = {
             use std::io::Read;
         let mut s = String::new();
         std::io::stdin().read_to_string(&mut s).unwrap();
         s
     };
     let mut iter = s.split_whitespace();
     input_inner!{iter, $($r)*}
     };
}
     
macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
 
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}
 
macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
 
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
 
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
 
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
 
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_imports)]
use std::cmp::{max, min, Ordering};
#[allow(unused_imports)]
use std::collections::{VecDeque, HashMap, BTreeMap, HashSet, BTreeSet};
#[allow(unused_imports)]
use std::io::{stdout, Write, BufWriter};
//#[allow(unused_imports)]
//use proconio::marker::{Isize1, Usize1, Bytes, Chars};
//#[proconio::fastout]
fn main() {
    input!{
        x: u64,
    }
    let x = x as f64;
    let mut ans = 1;
    for i in 1..(x.sqrt().floor() as u64 + 1u64) {
        let (power_l, power_g) = (i.pow(x.log(i as f64).floor() as u32), i.pow(x.log(i as f64).ceil() as u32));
        let power = if power_g <= x as u64 { power_g }
        else { power_l };
        ans = max(ans, power);
    }
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int n, m;
    cin >> n >> m;
    int sum = 0;
    for(int i = 0; i < m; i++) {
        int x;
        cin >> x;
        sum += x;
    }
    cout << (sum <= n ? (n - sum) : -1);
 
    return 0;
}

Measured memory_bytes: 3636
A=int(input())
B=int(input())

if (A==1) and (B==2):
    print(3)
elif (A==1) and (B==3):
    print(2)
elif (A==2) and (B==1):
    print(3)
elif (A==2) and (B==3):
    print(1)
elif (A==3) and (B==1):
    print(2)
elif (A==3) and (B==2):
    print(1)


Measured memory_bytes: 38256
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <functional>
#define fs first
#define se second

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;
typedef pair<ld, ld> pdd;

int n;
pii A[200000];
int ans[200000];
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> A[i].first;
        A[i].second = i;
    }
    sort(A, A + n);
    for (int i = 0; i + i < n; ++i) ans[A[i].second] = A[n >> 1].first;
    for (int i = n >> 1; i < n; ++i) ans[A[i].second] = A[(n >> 1) - 1].first;
    for (int i = 0; i < n; ++i) printf("%d\n", ans[i]);
    return 0;
}

Measured memory_bytes: 4608
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    string s, t;
    cin >> s >> t;
    int m = s.size(), n = t.size();
    vector<vector<int>> dp(m + 1, vector<int> (n + 1, 0));
    vector<vector<pair<int, int> >> f(m + 1, vector<pair<int, int>> (n + 1, make_pair(0, 0)));
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (s[i - 1] == t[j - 1] && dp[i - 1][j - 1] + 1 > dp[i][j]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                f[i][j] = pair<int, int>(i - 1, j - 1);
            }
            if (dp[i - 1][j] > dp[i][j]) {
                dp[i][j] = dp[i - 1][j];
                f[i][j] = pair<int, int>(i - 1, j);
            }
            if (dp[i][j - 1] > dp[i][j]) {
                dp[i][j] = dp[i][j - 1];
                f[i][j] = pair<int, int>(i, j - 1);
            }
        }
    }
    string res = "";
    int i = m, j = n;
    while (i != 0 && j != 0) {
        auto t = f[i][j];
        int ti = t.first, tj = t.second;
        if (ti == i - 1 && tj == j - 1 && dp[i][j] != 0) {
            res.push_back(s[i - 1]);
        }
        i = ti;
        j = tj;
    }
    reverse(res.begin(), res.end());
    cout << res << endl;
}

Measured memory_bytes: 105984
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

int main(){
  int a , b , c;
  cin >> a >> b >> c;
  cout << (a - b) % c << endl;
}


Measured memory_bytes: 256
import numpy as np
N, W = map(int, input().split())
ndp = np.full(1000*100+1, 10**11, dtype=np.int64)
ndp[0] = 0

for _ in range(N):
    w, v = map(int,input().split())

    np.minimum(ndp[:-v] + w, ndp[v:], out = ndp[v:])

print(np.max(np.where(ndp<=W)))

"""
https://atcoder.jp/contests/dp/submissions/6646897
から失敬

貪欲法はこの手の書き方で表現できるっぽい。
価値テープのなかで同価値のindexでは、より少ない重量の物品で済む方を残していく。
したがってテープの初期化は擬似infで行い、価値0の部分は重さも0で始める。

"""


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

int main(void){
    string S; cin >> S;
    
    if(S == "Sunny"){
        printf("Cloudy");
    }else if(S == "Rainy"){
        printf("Sunny");
    }else if(S == "Cloudy"){
        printf("Rainy");
    }
    
    return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define EPS (1e-7)
#define INF (1e9)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) x.begin(),x.end()
#define pii pair<int, int>
#define pll pair<long long, long long>
const double PI = acos(-1);
const ll MOD = 1000000007;
// const ll MOD = 998244353;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}
 
template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
///////////////////////////////////////////////////////////////

template< typename T >
struct edge {
    int to;
    T cost;

    edge(int to, T cost) : to(to), cost(cost) {}
};

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int N,M,s,t; cin >> N >> M >> s >> t;
    s--; t--;
    vector<vector<edge<ll>>> A(N),B(N);
    rep(i,M) {
        int u,v,a,b; cin >> u >> v >> a >> b;
        u--; v--;
        A[u].emplace_back(v,a);
        A[v].emplace_back(u,a);
        B[u].emplace_back(v,b);
        B[v].emplace_back(u,b);
    }

    vector<ll> distA(N,1e18),distB(N,1e18);
    distA[s] = 0; distB[t] = 0;
    priority_queue<pll, vector<pll>, greater<pll>> pq;

    pq.emplace(0,s);
    while (!pq.empty()) {
        ll D,v;
        tie(D,v) = pq.top(); pq.pop();
        if (D > distA[v]) continue;
        for (auto e : A[v]) {
            if (chmin(distA[e.to], distA[v]+e.cost)) pq.emplace(distA[e.to],e.to);
        } 
    }
    pq.emplace(0,t);
    while (!pq.empty()) {
        ll D,v;
        tie(D,v) = pq.top(); pq.pop();
        if (D > distB[v]) continue;
        for (auto e : B[v]) {
            if (chmin(distB[e.to], distB[v]+e.cost)) pq.emplace(distB[e.to],e.to);
        } 
    }

    vector<ll> ans(N);
    ans[N-1] = distA[N-1] + distB[N-1];
    for (int i = N-2; i >= 0; i--) {
        ans[i] = min(ans[i+1],distA[i]+distB[i]);
    }

    rep(i,N) cout << 1000000000000000 - ans[i] << endl;
}


Measured memory_bytes: 19576
#include "bits/stdc++.h"

using namespace std;
typedef long long int ll;
typedef pair<ll, ll > pi;  
typedef pair<pair<ll, ll >, ll > pii;  
vector<ll > vec;
vector<vector<ll > > vec2;
ll MOD = 1000000007;
ll INF = 1145141919454519;

int main(){

    ll A, B, M;
    cin >> A >> B >> M;

    vector<ll > a(A, 0);
    vector<ll > b(B, 0);

    ll ans = INF;

    ll mna = INF;
    for(ll i = 0; i < A; i++){
        cin >> a[i];
        mna = min(a[i], mna);
    }

    ll mnb = INF;
    for(ll i = 0; i < B; i++){
        cin >> b[i];
        mnb = min(b[i], mnb);
    }

    ans = mna + mnb;
    for(ll i = 0; i < M; i++){
        ll x, y, c; cin >> x >> y >> c;
        ans = min(ans,a[x-1]+b[y-1]-c);
    }

    cout << ans << endl;

}

Measured memory_bytes: 1792
#include <iostream>
using namespace std;
int main()
{
    int n,k,x,y;
    cin >> n;
    cin >> k;
    cin >> x;
    cin >> y;

    int ans;
    if ( n <= k ){
        ans = n * x;
    }else{
        ans = k * x + (n-k) * y;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iomanip>
#include <random>
#include <time.h>
#include <vector>
#include <math.h>
#include <algorithm>
#include <queue>
#include <functional>
#include <map>
#include <string>
#include <cstdlib>
#include <typeinfo>
#include <iostream>
using namespace std;
int main()
{
	long long int sx, sy, tx, ty, a, b;
	cin >> sx >> sy >> tx >> ty;
	a = abs(sx - tx);
	b = abs(sy - ty);
	for (int i = 0; i < a; i++) cout << 'R';
	for (int i = 0; i < b; i++) cout << 'U';
	for (int i = 0; i < a; i++) cout << 'L';
	for (int i = 0; i <= b; i++) cout << 'D';
	for (int i = 0; i <= a; i++) cout << 'R';
	for (int i = 0; i <= b; i++) cout << 'U';
	cout << "LU";
	for (int i = 0; i <= a; i++) cout << 'L';
	for (int i = 0; i <= b; i++) cout << 'D';
	cout << 'R' << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &t) {
	t=0; char ch=getchar(); int f=1;
	while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f;
}
typedef long long ll;
const int maxn=(2e5)+10;
int tmp,n,tot,d[maxn],k,cnt,dp[maxn],e[maxn];
ll b,ans;
int f(int &x,int y) {
	x+=y;
	if (x>=10) { x-=9; return 2; }
	return 1;
}
int solve() {
	for (int i=tot-1;i>=1;i--)
		ans+=f(d[i],d[i+1]);
	return d[1];
}
int main() {
	//freopen("1.txt","r",stdin);
	/*for (int n=10;n<maxn;n++) {
		int m=n;
		tot=0;
		int lst=0;
		while (m) d[++tot]=m%10,m/=10;
		reverse(d+1,d+tot+1);
		for (int i=1;i<tot;i++) {
			tmp=0;
			for (int j=1;j<i;j++)
				tmp=tmp*10+d[j];
			k=d[i]+d[i+1];
			if (k<10) tmp=tmp*10+k;
			else tmp=tmp*100+k;
			//if (n==973) printf("%d %d\n",tmp,k);
			for (int j=i+2;j<=tot;j++)
				tmp=tmp*10+d[j];
			//printf("%d %d\n",tmp,dp[tmp]);
			if (!lst) lst=dp[tmp];
			else if (lst!=dp[tmp]) printf("WA\n");
			dp[n]=max(dp[n],dp[tmp]+1);
		}
		//printf("n=%d dp=%d\n",n,dp[n]);
	}*/
	//printf("%d\n",dp[9888]);
	/*123499
	123418
	12349
	12313
	1234
	127
	129
	39
	12
	3*/
	read(n); int r,a;
	for (int i=1;i<=n;i++) {
		read(a); read(b);
		tot=0;
		while (b>1) {
			if (b&1) d[++tot]=a;
			r=a;
			tmp=f(a,r);
			b/=2; ans+=b*tmp;
		}
		d[++tot]=a;
		reverse(d+1,d+tot+1);
		e[i]=solve();
	}
	tot=n;
	for (int i=1;i<=n;i++) d[i]=e[i];
	solve();
	printf("%lld\n",ans);
	return 0;
}
/*
  REMEMBER:
  1. Think TWICE, Code ONCE!
  Are there any counterexamples to your algo?
    
  2. Be careful about the BOUNDARIES!
  N=1? P=1? Something about 0?
    
  3. Do not make STUPID MISTAKES!
  Array size? Integer overflow? Time complexity? Memory usage? Precision error?
*/

Measured memory_bytes: 1792
#include <iostream>
#define int long long
using namespace std;
const int maxn = 1e6 + 5;
int a[maxn], N;
int f(int x, int y, int z){
    return x * x + y * y + z * z + x * y + y * z + z * x; 
}


signed main(){
    cin >> N;
    for(int x = 1; x <= 100; ++x){
        for(int y = 1; y <= 100; ++y){
            for(int z = 1; z <= 100; ++z){
                int p = f(x, y, z);
                if(p > N) continue;
                a[p] ++;
            }
        }
    }
    for(int i = 1; i <= N; ++i) cout << a[i] << "\n";
    return 0;
}

Measured memory_bytes: 3660
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }

ll lcm(ll a, ll b) { return a * b / gcd(a, b); }

int main()
{
  ll A, B, C, D;
  cin >> A >> B >> C >> D;
  ll a = B / C - (A-1) / C;
  ll b = B / D - (A-1) / D;
  ll c = lcm(C, D);
  ll m = max((ll)0, (B/c - (A-1)/c));
  cout << B - (A-1) - (a + b - m) << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int N=4010,M=1000010,P=998244353;
const int inf=0x3f3f3f3f;
const int INF=0xcfcfcfcf;
const double eps=1e-6,pi=asin(1)*2;
inline ll read();
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
inline int ADD(int a,int b) { return a+b>=P?a+b-P:a+b; }
inline int MINUS(int a,int b) { return a-b<0?a-b+P:a-b; }
#define plus(a,b) a=ADD(a,b)
#define minus(a,b) a=MINUS(a,b)
#define mul(a,b) a=(a*(b))%P
#define mem(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
#define pil pair<int,ll>
#define pli pair<ll,int>
#define pll pair<ll,ll>
#define mp(x,y) make_pair(x,y)

int K,n;
int C[N][N];
inline void init(int n=4000)
{
	for(int i=0;i<=n;i++)
	{
		C[i][0]=1;
		for(int j=1;j<=i;j++) C[i][j]=ADD(C[i-1][j-1],C[i-1][j]);
	}
}

const int sign[]={1,P-1};

#ifdef FILE
char buf[1<<25],*p1=buf,*p2=buf;
#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<25,stdin),p1==p2)?EOF:*p1++
#endif
inline ll read()
{
	ll s=0;
	bool flag=false;
	char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') flag=true;
	for(;'0'<=ch&&ch<='9';ch=getchar()) s=(s<<3)+(s<<1)+(ch^'0');
	if(flag) return -s;
	return s;
}

int main()
{
#ifdef FILE
	freopen(FILE ".in","r",stdin);
	freopen(FILE ".out","w",stdout);
#endif
	K=read(),n=read();
	init();
	for(int k=2;k<=2*K;k++)
	{
		int p=min(k/2,K-(k-1)/2);
		int ans=0;
		for(int i=0;i<=p;i++) plus(ans,1ll*sign[i&1]*C[p][i]%P*C[n-2*i+K-1][K-1]%P);
		printf("%d\n",ans);
	}
	return 0;
}

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

int main() {
  int n,m;
  int count = 0;
  cin >> n >> m;
  vector<long long> h(n);
  vector<int> a(m);
  vector<int> b(m);
  vector<int> ng(n);
  rep(i,n)
    cin >> h.at(i);
  rep(j,m)
    cin >> a.at(j) >> b.at(j);

  rep(j,m){
    if(h.at(a.at(j)-1) > h.at(b.at(j)-1)){
      ng.at(b.at(j)-1) = 1;
    }else if(h.at(a.at(j)-1) < h.at(b.at(j)-1)){
      ng.at(a.at(j)-1) = 1;
    }else{
      ng.at(a.at(j)-1) = 1;
      ng.at(b.at(j)-1) = 1;
    }
  }
  rep(i,n){
    if(ng.at(i) == 0){
      count++;
    }
  }
  cout << count << endl;
  
}


Measured memory_bytes: 5052