akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define REP(i,n) for (ll i = 0; i < (n); ++i)
#define RREP(i, n) for (ll i = (n) - 1; i >= 0; --i)
#define ALL(v) (v).begin(), (v).end()


const ll INF = numeric_limits<ll>::max();

int main(){
    ll n, m, s;
    cin >> n >> m >> s;

    vector<vector<array<ll, 3>>> net(n);  // nxt, ai, bi
    vector<ll> c(n), d(n);

    ll ub = 0;

    REP(i, m){
        ll ui, vi, ai, bi;
        cin >> ui >> vi >> ai >> bi;
        ui--; vi--;
        net.at(ui).push_back({vi, ai, bi});
        net.at(vi).push_back({ui, ai, bi});

        ub += ai;
    }

    REP(i, n){
        cin >> c.at(i) >> d.at(i);
    }

    vector<vector<ll>> mintime(n, vector(ub + 1, INF));
    s = min(s, ub);
    mintime.at(0).at(s) = 0;
    priority_queue<array<ll, 3>, vector<array<ll, 3>>, greater<array<ll, 3>>> que;
    que.push({0, 0, s});
    while(!que.empty()){
        const auto [tcur, cur, ccur] = que.top(); que.pop();
        if(tcur > mintime.at(cur).at(ccur)){ continue; }
        for(const auto [nxt, ai, bi] : net.at(cur)){
            if(ccur < ai){ continue; }
            const ll t2 = tcur + bi;
            const ll c2 = ccur - ai;
            if(t2 < mintime.at(nxt).at(c2)){
                mintime.at(nxt).at(c2) = t2;
                que.push({t2, nxt, c2});
            }
        }

        for(ll i = 1; i <= 1; ++i){
            const ll t2 = tcur + d.at(cur) * i;
            const ll c2 = min(ccur + c.at(cur) * i, ub);
            if(t2 < mintime.at(cur).at(c2)){
                mintime.at(cur).at(c2) = t2;
                que.push({t2, cur, c2});
            }
        }
    }

    for(ll i = 1; i < n; ++i){
        cout << *min_element(ALL(mintime.at(i))) << endl;
    }
    return 0;
}


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

using namespace std;

const int N = 200 * 1000 + 17;
const int MOD = 1000 * 1000 * 1000 + 7;
const int M = 998244353;

int n;
int deg[N];
vector<int> g[N];

bool read() {
    if (!(cin >> n))
        return false;

    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        g[u - 1].emplace_back(v - 1);
        g[v - 1].emplace_back(u - 1);
    }

    return true;
}

vector<int> dfs_d(int v, int pr, vector<int> path) {
    path.emplace_back(v);
    auto res = path;

    for (auto to : g[v])
        if (to != pr) {
            auto ret = dfs_d(to, v, path);

            if (ret.size() > res.size())
                res = ret;
        }

    return res;
}

void dfs(int v, int pr, int h = 0) {
    deg[h] = max(deg[h], (int) g[v].size() - (pr != -1));

    for (auto to : g[v])
        if (to != pr)
            dfs(to, v, h + 1);
}

void solve() {
    auto D = dfs_d(dfs_d(0, -1, vector<int>()).back(), -1, vector<int>());
    cout << (1 + D.size()) / 2 << ' ';

    if (D.size() % 2 == 0) {
        dfs(D[D.size() / 2 - 1], D[D.size() / 2]);
        dfs(D[D.size() / 2], D[D.size() / 2 - 1]);
        auto ans = 2ll;

        for (int i = 0; i < D.size() / 2 - 1; ++i)
            ans *= deg[i];

        cout << ans << endl;
    } else {
        auto v = D[D.size() / 2];
        dfs(v, -1);
        auto ans = 1ll;

        for (int i = 0; i < D.size() / 2; ++i)
            ans *= deg[i];

        for (const auto& u : g[v]) {
            fill(deg, deg + n, 0);
            auto cur = 2ll;
            dfs(u, v);
            dfs(v, u);

            for (int i = 0; i < D.size() / 2; ++i)
                cur *= deg[i];

            if (cur != 0)
                ans = min(ans, cur);
        }

        cout << ans << endl;
    }
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    while (read())
        solve();

    return 0;
}



Measured memory_bytes: 4992
list_ = [0]
n, min_count = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
kind = 1
tmp = a[0]
for i in range(n):
    if(tmp != a[i]):
        kind += 1
        tmp = a[i]
        list_.append(0)
    list_[kind - 1] += 1
ans = 0
list_.sort()
idx = 0
for i in range(kind - min_count):
    ans += list_[idx]
    idx += 1
print(ans)

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

#define rep(i, n) for(int i = 0; i < (n); i++)
using LL = long long;
using ULL = unsigned long long;


void solve() {
	int n; cin >> n;
	vector<ULL> a(n + 1);
	for (int i = 1; i <= n; i++) {
		cin >> a[i]; a[i] += a[i - 1];
	}
	ULL A = a[n];
	ULL L, R;
	for (int i = 1; i <= n; i++) {
		if (a[i] * 2 >= A) {
			L = a[i - 1];
			R = a[i];
			break;
		}
	}

	ULL ans = min(A - L * 2, R * 2 - A);

	cout << ans << endl;
}

int main() {

	solve();

	return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
const int N=105,M=10005;
bool vis[N][N][M*2];
int n,m,val[N][N];
int ans=1e9;
void work(int x,int y,int now){
	if (vis[x][y][now+M]) return;
	vis[x][y][now+M]=true;
	if (x==n&&y==m) {
		ans=min(ans,abs(now-val[x][y]));
		ans=min(ans,abs(now+val[x][y]));
		return;
	}
	if (x!=n) {
		work(x+1,y,now+val[x][y]);
		work(x+1,y,now-val[x][y]);
	}
	if (y!=m) {
		work(x,y+1,now+val[x][y]);
		work(x,y+1,now-val[x][y]);
	}
}
int main (){
	scanf ("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			scanf ("%d",&val[i][j]);
	for (int i=1,x;i<=n;i++)
		for (int j=1;j<=m;j++)
			scanf ("%d",&x),val[i][j]=abs(val[i][j]-x);
	work(1,1,0);
	printf ("%d",ans);
	return 0;
}

Measured memory_bytes: 164096
import java.util.Scanner;
import java.util.Arrays;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String[] strList = new String[n];
        for(int i = 0; i<n; i++){
            strList[i] = sc.next();
        }
        
        Arrays.sort(strList);
        int count = 0;

        count++;
        for(int i = 0; i<n-1; i++){
            if(!strList[i].equals(strList[i+1])){
                count++;
            }
        }
        System.out.println(count);
    }
}

Measured memory_bytes: 71044
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (ll i = a; i < b; i++)
#define REP(i,b) FOR(i,0,b)
#define RFOR(i,a,b) for (ll i = a-1; i >= b; i--)
#define RREP(i,a) RFOR(i,a,0)
#define REPALL(i,x) for (ll i = 0; i < x.size(); i++)
#define RREPALL(i,x) for (ll i = x.size()-1; i >= 0; i--)
#define REPITR(itr,x) for (auto itr = (x).begin(); itr != (x).end(); itr++)
#define ALL(x) (x).begin(), (x).end()
#define SORT(x) sort(ALL(x))
#define MIN_ELEMENT(x) min_element(ALL(x))
#define MAX_ELEMENT(x) max_element(ALL(x))
#define COUNT(x,num) count(ALL(x), num)
#define MEMSET(x,val) memset(x, val, sizeof(x))
#define MAX(a,b) a = max(a,b)
#define MIN(a,b) a = min(a,b)
#define debug(x) cerr<<__LINE__<<": "<<(#x)<<" = "<<(x)<<endl;
void YES(bool flag) {cout<<(flag ? "YES" : "NO")<<endl;}
void Yes(bool flag) {cout<<(flag ? "Yes" : "No")<<endl;}
void yes(bool flag) {cout<<(flag ? "yes" : "no")<<endl;}
#define e1 first
#define e2 second
#define nextline putchar('\n')
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
typedef vector<ll> VLL;
typedef vector<vector<ll>> VVLL;
const int INF = 1e7;
const ll MOD = 1e9 + 7;

int main()
{
    string s;
    cin>>s;
    bool flag = (s.size() % 2 == 0);
    REPALL(i,s) {
        if ((i % 2 == 0 && s[i] != 'h') || (i % 2 == 1 && s[i] != 'i')) {
            flag = false;
            break;
        }
    }
    Yes(flag);

    return 0;
}


Measured memory_bytes: 256
def main():
    import sys
    input = sys.stdin.readline

    H, W, D = map(int, input().split())
    A = [[int(x) for x in input().split()] for _ in range(H)]

    B = [0] * (H * W)

    C = [None] * (H * W)
    for r, row in enumerate(A):
        for c, cell in enumerate(row):
            C[cell - 1] = r, c

    for x in range(D, H * W):
        L, R = x - D, x
        lr, lc = C[L]
        rr, rc = C[R]
        B[R] = B[L] + abs(rr - lr) + abs(rc - lc)

    ans = []
    Q = int(input())
    for _ in range(Q):
        L, R = (int(x) - 1 for x in input().split())
        ans.append(B[R] - B[L])

    print(*ans, sep='\n')


if __name__ == '__main__':
    main()


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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second

using vint=vector<int>;
using pint=pair<int,int>;
using vpint=vector<pint>;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

template<class A,class B>
ostream& operator<<(ostream& ost,const pair<A,B>&p){
	ost<<"{"<<p.first<<","<<p.second<<"}";
	return ost;
}

template<class T>
ostream& operator<<(ostream& ost,const vector<T>&v){
	ost<<"{";
	for(int i=0;i<v.size();i++){
		if(i)ost<<",";
		ost<<v[i];
	}
	ost<<"}";
	return ost;
}

inline int topbit(unsigned long long x){
	return x?63-__builtin_clzll(x):-1;
}

inline int popcount(unsigned long long x){
	return __builtin_popcountll(x);
}

inline int parity(unsigned long long x){
	return __builtin_parity(x);
}

int N;
string S;

int calc(int M){
	vint A(N+1);
	rep(i,N){
		A[i+1]=A[i];
		if(S[i]=='1')A[i+1]++;
		else A[i+1]--;
	}
	vint suf=A;
	for(int i=N-1;i>=0;i--)chmax(suf[i],suf[i+1]);

	int offset=0;
	int mi=0;
	rep(i,N){
		if(S[i]=='?'&&suf[i+1]+offset+2<=M)offset+=2;
		chmin(mi,A[i+1]+offset);
	}
	return M-mi;
}

signed main(){
	cin>>S;
	N=S.size();

	int cur=0;
	int m=0;
	rep(i,N){
		if(S[i]=='1')cur++;
		else cur--;
		chmax(m,cur);
	}

	cout<<min(calc(m),calc(m+1))<<endl;
	return 0;
}

Measured memory_bytes: 20084
h,w=map(int,input().split())
n=int(input())
a=list(map(int,input().split()))
ans=[[0]*w for _ in range(h)]
num=-1
for i in range(n):
    for j in range(a[i]):
        num+=1
        if (num//h)%2==1:
            ans[h-1-num%h][num//h]=i+1
        else:
            ans[num%h][num//h]=i+1
for i in range(h):
    print(*ans[i])


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

int main()
{
  vector<vector<int>>A(3,vector<int>(3)) ;
  for(int i=0;i<3;i++) for(int j=0;j<3;j++) cin>>A.at(i).at(j) ;
  int N ;
  cin>>N ;
  vector<int>B(N) ;
  for(int i=0;i<N;i++) cin>>B.at(i) ;
  
  for(int i=0;i<3;i++){
    for(int j=0;j<3;j++){
      for(int k=0;k<N;k++){
        if(A.at(i).at(j)==B.at(k)){
          A.at(i).at(j)=0 ;
          break ;
        }
      }
    }
  }
  
  vector<int>C(8,0) ;
  for(int i=0;i<3;i++){
    C.at(0)+=A.at(0).at(i) ;
    C.at(1)+=A.at(1).at(i) ;
    C.at(2)+=A.at(2).at(i) ;
    C.at(3)+=A.at(i).at(0) ;
    C.at(4)+=A.at(i).at(1) ;
    C.at(5)+=A.at(i).at(2) ;
    C.at(6)+=A.at(i).at(i) ;
    C.at(7)+=A.at(2-i).at(i) ;
  }
  
  for(int i=1;i<8;i++){
    if(C.at(i)==0){
      cout<<"Yes"<<endl ;
      return 0 ;
    }
  }

  cout<<"No"<<endl ; 
  
  return 0 ;
}


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

int main(){
    string s;
    cin >> s;
    if(s=="Sunny"){
        cout << "Cloudy" << endl;
    }else if(s=="Cloudy"){
        cout << "Rainy" << endl;
    }else if(s=="Rainy"){
        cout << "Sunny" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
using namespace std;

#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)
#define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--)
#define all(v) begin(v), end(v)
#define pb(a) push_back(a)
#define fr first
#define sc second
#define INF 2000000000
#define int long long int

#define X real()
#define Y imag()
#define EPS (1e-10)
#define EQ(a,b) (abs((a) - (b)) < EPS)
#define EQV(a,b) ( EQ((a).X, (b).X) && EQ((a).Y, (b).Y) )
#define LE(n, m) ((n) < (m) + EPS)
#define LEQ(n, m) ((n) <= (m) + EPS)
#define GE(n, m) ((n) + EPS > (m))
#define GEQ(n, m) ((n) + EPS >= (m))

typedef vector<int> VI;
typedef vector<VI> MAT;
typedef pair<int, int> pii;
typedef long long ll;

typedef complex<double> P;
typedef pair<P, P> L;
typedef pair<P, double> C;

int dx[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};
int const MOD = 1000000007;
ll mod_pow(ll x, ll n) {return (!n)?1:(mod_pow((x*x)%MOD,n/2)*((n&1)?x:1))%MOD;}
int madd(int a, int b) {return (a + b) % MOD;}
int msub(int a, int b) {return (a - b + MOD) % MOD;}
int mmul(int a, int b) {return (a * b) % MOD;}
int minv(int a) {return mod_pow(a, MOD-2);}
int mdiv(int a, int b) {return mmul(a, minv(b));}

namespace std {
    bool operator<(const P& a, const P& b) {
        return a.X != b.X ? a.X < b.X : a.Y < b.Y;
    }
}

int link[10][10];
int dp[1<<10][10];
signed main() {
    memset(link, 0, sizeof(link));
    int N, M; cin >> N >> M;
    rep(i,0,M) {
        int a, b; cin >> a >> b;
        a--; b--;
        link[a][b] = 1;
        link[b][a] = 1;
    }

    memset(dp, 0, sizeof(dp));
    dp[1][0] = 1;
    rep(i,0,1<<N) {
        rep(j,0,N) {
            rep(k,0,N) {
                if(j == k) continue;
                if(i >> k & 1) continue;
                if(link[j][k] == 0) continue;
                int nbit = i | (1 << k);
                dp[nbit][k] += dp[i][j];   
            }
        }
    }
    int ans = 0;
    rep(i,0,N) ans += dp[(1<<N)-1][i];
    cout << ans << endl;
    return 0;
}

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

using namespace std;

const int N = 2e5+7, mod = 2019;
int T[N], cnt[N];

int main(){
#ifdef LOCAL
	freopen("input", "r", stdin);
#endif

	string s;

	cin >> s;

	int n = s.size();

	T[n] = 0;
	cnt[0]++;
	
	int pot = 1;

	for (int i=n-1;i>=0;i--){
		T[i] = (T[i+1] % mod + ( (s[i]-'0') * pot%mod ) % mod) % mod;
		pot = (pot%mod * 10)%mod;
		cnt[T[i]]++;
	}

	long long int ans = 0;

	for (int i=0;i<N;i++){
		ans += cnt[i]*(cnt[i]-1)/2;
	}

	printf("%lld\n", ans);

	return 0;
}

Measured memory_bytes: 4504
#include <bits/stdc++.h>
using namespace std;
using ll = long long; // ll は long long　と同じとする。(int64_t)
int main(){
    int R;
    cin >> R;
    cout << fixed << setprecision(20) << R * 2 * 3.14159265358979323846 << endl;
}

Measured memory_bytes: 3776
n = int(input())
s = []
for i in range(n):
    s.append(''.join(sorted(list(input()))))
s.sort()

ans = 0
count = 1
s_pre = s[0]

for i in range(1, n):
    if s_pre == s[i]:
        count += 1
    else:
        ans += int(count * (count - 1) / 2)
        s_pre = s[i]
        count = 1

ans += int(count * (count - 1) / 2)
print(int(ans))

Measured memory_bytes: 10736
#include <stdio.h>

int main(){
  int h,w;
  scanf("%d%d",&h,&w);
  char s[h][w+1];
  int i=0;
  for(i=0;i<h;i++){
    scanf("%s",s[i]);
  }
  int count[h][w];
  int j=0;
  for(i=0;i<w;i++){
    for(j=0;j<h;j++){
      count[j][i] = 0;
    }
  }
  int count_num = h * w;
  long long int ans = 0;
  for(i=0;i<h;i++){
    for(j=0;j<w;j++){
      if(count_num == 0){
        break;
      }
      if(count[i][j] == 0){
        //printf("(%d,%d) %c\n",i,j,s[i][j]);
        count[i][j] = 1;
        int tmp[h*w][2];
        int tmp_num = 1;
        tmp[0][0] = i;
        tmp[0][1] = j;
        int black = 0;
        int white = 0;
        if(s[i][j]=='#'){
          black++;
        }else{
          white++;
        }
        while(tmp_num > 0){
          tmp_num--;
          int tmp_i = tmp[tmp_num][0];
          int tmp_j = tmp[tmp_num][1];
          //printf("(%d %d) %c ",tmp_i,tmp_j,s[tmp_i][tmp_j]);
          if(tmp_i > 0 && count[tmp_i-1][tmp_j] == 0 && (s[tmp_i-1][tmp_j] != s[tmp_i][tmp_j])){
            if(s[tmp_i-1][tmp_j]=='#'){
              black++;
            }else{
              white++;
            }
            count[tmp_i-1][tmp_j] = 1;
            tmp[tmp_num][0] = tmp_i-1;
            tmp[tmp_num][1] = tmp_j;
            tmp_num++;
          }
          if(tmp_j > 0 && count[tmp_i][tmp_j-1] == 0 && (s[tmp_i][tmp_j-1] != s[tmp_i][tmp_j])){
            if(s[tmp_i][tmp_j-1]=='#'){
              black++;
            }else{
              white++;
            }
            count[tmp_i][tmp_j-1] = 1;
            tmp[tmp_num][0] = tmp_i;
            tmp[tmp_num][1] = tmp_j-1;
            tmp_num++;
          }
          if(tmp_i < h-1 && count[tmp_i+1][tmp_j] == 0 && (s[tmp_i+1][tmp_j] != s[tmp_i][tmp_j])){
            if(s[tmp_i+1][tmp_j]=='#'){
              black++;
            }else{
              white++;
            }
            count[tmp_i+1][tmp_j] = 1;
            tmp[tmp_num][0] = tmp_i+1;
            tmp[tmp_num][1] = tmp_j;
            tmp_num++;
          }
          if(tmp_j < w-1 && count[tmp_i][tmp_j+1] == 0 && (s[tmp_i][tmp_j+1] != s[tmp_i][tmp_j])){
            if(s[tmp_i][tmp_j+1]=='#'){
              black++;
            }else{
              white++;
            }
            count[tmp_i][tmp_j+1] = 1;
            tmp[tmp_num][0] = tmp_i;
            tmp[tmp_num][1] = tmp_j+1;
            tmp_num++;
          }
        }
        ans += (long long int) black * white;
        //printf("black %d white %d\n", black,white);
      }
    }
  }
  printf("%lld",ans);
  return 0;
}


Measured memory_bytes: 1536
#include <stdio.h>
int main()
{
    char s[100];
    scanf("%s", s);
    if (s[0] == 'S')
        printf("Cloudy\n");
    else if (s[0] == 'C')
        printf("Rainy\n");
    else
        printf("Sunny\n");
    return 0;
}

Measured memory_bytes: 128
import java.io.*;
import java.util.*;


// 44 27.672
// 46 33.227 240 2011/10/28
// 2011/10/29

// 0107 `[Y
public class Main {

	// C return falseÅ¨µÜ¢
	boolean main() throws IOException {

		int[] ir = readIntArray();
		if (ir[0] == 0 && ir[1] == 0 && ir[2] == 0)
			return false;
		Arrays.sort(ir);
		
		int n = readIntArray()[0];
		for(int i = 0; i < n; i++) {
			int r = readIntArray()[0];
			
			boolean isOK = false;
			if (ir[0] * ir[0] + ir[1] * ir[1] < r * r * 4)
				isOK = true;
			
			System.out.printf("%s\n", isOK ? "OK":"NA");
		}
		
		return true; // ³íI¹ Ö
	}
	

//	private final static boolean DEBUG = true;  // debug
	private final static boolean DEBUG = false; // release

	public static void main(String[] args) throws IOException {

		if (DEBUG) {
			log = System.out;
			
			String inputStr = "10 6 8:5:4:8:6:2:5:0 0 0:";
			
			inputStr = inputStr.replace(":", "\n");

			reader = new BufferedReader(new StringReader(inputStr)); 

		}
		else {
			log = new PrintStream(new OutputStream() { public void write(int b) {} } ); // «ÌÄ
			reader = new BufferedReader(new InputStreamReader(System.in)); // R\[©ç
		}
		
		int N = Integer.MAX_VALUE;
		//int N = readIntArray()[0];

		for(int i = 0; i < N; i++) {
			boolean b = new Main().main();
			if (!b)
				break;
		}		
		
		reader.close();
	}

	
	static PrintStream log;
	static BufferedReader reader;
	

	// WüÍæè1sªÌæØè¶æØèÅÌ®lðÇÞ
	// EOFÌêÍnullðÔ·
	private static int[] readIntArray() throws IOException {

		String s = null;
		for(;;) {
			s = reader.readLine();
//			log.printf("%s\n", s);
			if (s == null)
				return null;
			s = s.trim();
			if (s.length() != 0) // ¦¦¦@Ç¤àËRósðÇÞ±Æª éBÇÝòÎ·Æ¤Ü­¢­çµ¢BBBB
				break;
		}
		
		String[] sp = s.split("[ ,]"); // æØè¶ÍXy[X©J}
		int[] a = new int[sp.length];
		for(int i = 0; i < sp.length; i++) {
			a[i] = Integer.parseInt(sp[i]);
		}
		return a;
	}
		
}

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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}


int N,X;
int x[222222];

int cost(int n){
    int ret=N*X+n*X;

    int coef=0;
    for(int i=1;i<=N;i++){
        int d=x[N-i];
        if(i!=N)d-=x[N-i-1];

        if(i<=n){
            ret+=x[N-i];
            coef+=4;
        }
        else{
            int k=(i-1)/n;
            coef+=2*k+3;
        }
        ret+=coef*d;
    }
    return ret;
}

signed main(){
    cin>>N>>X;
    rep(i,N)cin>>x[i];


    int lb=0,ub=N;
    while(ub-lb>1){
        int mid=(ub+lb)/2;
        if(cost(mid+1)<=cost(mid))lb=mid;
        else ub=mid;
    }
    cout<<cost(ub)<<endl;
    return 0;
}


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

using namespace std;

int main() {
	int n, a, b, p, x = 0, y = 0, z = 0;
	cin >> n >> a >> b;
	for (int i = 0; i < n; i++) {
		cin >> p;
		if (p <= a) {
			x++;
		} else if (p <= b) {
			y++;
		} else {
			z++;
		}
	}
	cout << min(min(x, y), z) << '\n';
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define DAU  ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define PLEC return 0;
using namespace std;
int main() {
    DAU
    string s;
    cin >> s;
    char c = s[s.size() - 1];
    if (c == '3')
        cout << "bon";
    else if (c == '0' || c == '1' || c == '6' || c == '8')
        cout << "pon";
    else cout << "hon";
    PLEC
}


Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
#define inf INT_MAX
#define mod 1000000007
#define int long long

int path(int x, int y, int m, int n, vector<vector<int>> &dp) {
	if (x == m - 1 && y == n - 1)return 1;
	if (x >= m || y >= n)return 0;
	if (dp[x][y] != -1)return dp[x][y] % mod;
	return dp[x][y] = ((path(x + 1, y, m, n, dp) % mod) + (path(x, y + 1, m, n, dp) % mod)) % mod;
}

void solve() {
	int m, n;
	cin >> m >> n;
	char ch[m][n];
	int i, j;
	for (i = 0; i < m; i++) {
		for (j = 0; j < n; j++)cin >> ch[i][j];
	}
	vector<vector<int>> dp(m, vector<int>(n));
	for (i = 0; i < m; i++) {
		for (j = 0; j < n; j++) {
			if (ch[i][j] == '.')dp[i][j] = -1;
			else dp[i][j] = 0;
		}
	}
	cout << path(0, 0, m, n, dp) % mod << endl;
	return;
}

int32_t main() {

	std::ios::sync_with_stdio(false);
	cout.tie(0);
	cin.tie(0);
	int t = 1;
	// cin >> t;
	while (t--)solve();
	return 0;
}

Measured memory_bytes: 12152
def dfs(h, adj):
  splendid = 0
  visited = [0 for i in range(n)]
  stack = [i+1 for i in range(n)]
  while stack:
    x = stack.pop()
    if visited[x-1]:
      continue
    visited[x-1] = 1
    issplendid = 1
    for y in adj[x-1]:
      if h[y-1] >= h[x-1]:
        stack.append(y)
        issplendid = 0
    if issplendid:
      splendid += 1
  return splendid

n, m = map(int, input().split())
h = list(map(int, input().split()))
adj = [set() for _ in range(n)]
for _ in range(m):
  a, b = map(int, input().split())
  adj[a-1].add(b)
  adj[b-1].add(a)
print(dfs(h, adj))


Measured memory_bytes: 50140
N, K, L = [int(_) for _ in input().split()]


class UFT():
    def __init__(self):
        self.par = [i for i in range(N + 1)]
        self.rank = [0] * (N + 1)

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)


Road = UFT()
for _ in range(K):
    p, q = [int(_) for _ in input().split()]
    Road.unite(p, q)
Railway = UFT()
for _ in range(L):
    r, s = [int(_) for _ in input().split()]
    Railway.unite(r, s)
memo = {}
for i in range(1, N + 1):
    memo[Road.find(i) + N * Railway.find(i)] = memo.get(
        (Road.find(i) + N * Railway.find(i)), 0) + 1
print(' '.join(str(memo[Road.find(i) + N * Railway.find(i)])
               for i in range(1, N + 1)))


Measured memory_bytes: 52892
object Main extends App {
	override def main(args: Array[String]) = {
		val sc = new java.util.Scanner(System.in)
		
		val pw = new java.io.PrintWriter(System.out);
		
		Iterator.continually(new Rectangle(sc.nextInt,sc.nextInt))
			.takeWhile(_.isContinue)
			.foreach(_.print(pw))

		pw.flush
		
	}
	
	class Rectangle(val H: Int, val W:Int){
		val isContinue = !(H == 0 && W == 0)
		
		def print(pw : java.io.PrintWriter):Unit = {
			for(i <- (1 to H)){
				for(j <- (1 to W)){
					(i,j) match{
						case (1,_) | (H,_) =>
							pw.print("#")
						case (_,1) | (_,W) =>
							pw.print("#")
						case (_,_) => 
							pw.print(".")
					}
				}
				pw.println
			}
			pw.println
		}
		
	}
}

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

using namespace std;

using ll = long long;

const int MAX_V = 256;
const int INF = 1e8;

char lake[MAX_V][MAX_V];

struct edge {
    int  to;
    int  cap;
    int  rev;
};

vector<vector<edge>> G;
vector<bool> used;

void add_edge(int from, int to, int cap) {
    G[from].emplace_back((edge){to, cap, (int)G[to].size()});
    G[to].emplace_back((edge){from, 0, (int)(G[from].size() - 1)});
}

int dfs(int v, int t, int f) {
    if(v == t) return f;

    used[v] = true;
    for(edge& e : G[v]) {
        if(!used[e.to] && e.cap > 0) {
            int d = dfs(e.to, t, min(f, e.cap));
            if(d > 0) {
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}

int max_flow(int s, int t) {
    int flow = 0;
    while(true) {
        fill(used.begin(), used.end(), false);
        int f = dfs(s, t, INF);
        if(f == 0) return flow;  // 増加路が無いならフロー値を返す
        flow += f;
    }
}

int main() {
    int H, W;
    cin >> H >> W;

    int S = H+W;
    int T = H+W+1;

    G.resize(H+W+2);
    used.resize(H+W+2);

    for(int i = 0; i < H; i++) {
        for(int j = 0; j < W; j++) {
            cin >> lake[i][j];
            
            if(lake[i][j] == 'o') {
                add_edge(i, H+j, 1);
                add_edge(H+j, i, 1);
            }

            if(lake[i][j] == 'S') {
                add_edge(S, i, INF);
                add_edge(S, H+j, INF);
            }

            if(lake[i][j] == 'T') {
                add_edge(i, T, INF);
                add_edge(H+j, T, INF);
            }
        }
    }

    int ans = max_flow(S, T);
    if(ans >= INF) {
        cout << -1 << endl;
    } else {
        cout << ans << endl;
    }
}

Measured memory_bytes: 896
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
// memo  fixed  setprecision(20);
using vvll = vector<vector<ll>>;
ll mod =1e9+7;
/*"itob" int to "N"base */           template<typename TypeInt> string itob(const TypeInt v, int base){static const char table[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";string ret;static numeric_limits<TypeInt> t;TypeInt n = v;if (t.is_signed) {if (v < 0) n *= -1;}while (n >= base) {ret += table[n%base];n /= base;}ret += table[n];if (t.is_signed) {if (v < 0 && base == 10) ret += '-';}reverse(ret.begin(), ret.end());return ret;}
/*"chmin" a = MAX*/                  template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
/*"chmax" a = MIN*/                  template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
/*"ctoi"  char to int*/              int ctoi(char c) {return c-'0';}
/*"gcd"   MAX Euclidean */           ll gcd(ll a,ll b){if(b==0)return a; return gcd(b,a%b);}
/*"lcm"   MIN*/                      ll lcm(ll a,ll b){ll g = gcd(a,b);return a/g*b;}
/*"primecheck"If prime,return true.*/bool primecheck(ll n){if(n < 2) return false;else{for(int i = 2; i * i <= n; i++){if(n % i == 0) return false;}return true;}}
string  reverserange(string s,ll a,ll b){reverse(s.begin()+a-1,s.begin()+b); return s;}
ll modpow(ll a,ll n, ll mod){ll res = 1;while(n>0){if (n%2==1){res = res * a % mod;}a = a * a % mod;n/=2;}return res;}
int main() {
    ll x;
    cin >> x;
    for(int i=0;i<=10000;i++){
        for(int j=-10000;j<=10000;j++){
                ll a = pow(i,5);
                ll b = pow(j,5);
                ll che = a-b;
                if(che==x){
                    cout << i<<" "<<j<<endl;
                    return 0;
                }
        }
    }
}
    



Measured memory_bytes: 4228
n = int(input())
A = list(map(int,input().split()))
if n%2==0:
    B = A[1::2]
    C = A[::2]
    B = B[::-1]
    print(*(B+C))
else:
    B = A[::2]
    C = A[1::2]
    B = B[::-1]
    print(*(B+C))

Measured memory_bytes: 105380
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
using namespace std;
const int MX = 100005;
int n, a[MX], d[MX], rd[MX], ans;
int gcd(int a, int b){
	if(a < b) swap(a,b);
	for(;b;swap(a,b)) a %= b;
	return a;
}
int main(){
	scanf("%d", &n);
	rep(i,n){
		scanf("%d", a+i);
		d[i+1] = gcd(d[i], a[i]);
	}
	for(int i = n-1; i >= 0; i--){
		rd[i] = gcd(rd[i+1], a[i+1]);
		ans = max(ans,gcd(d[i], rd[i]));
	}
	printf("%d\n", ans);
}

Measured memory_bytes: 1408
#include "iostream"
#include "algorithm"
#include "string"
#include "vector"
#include "cmath"
#include "bitset"
#include "queue"
#include "functional"
#include "map"
#include "unordered_map"
#include "set"
#include "stack"

#define lp(n) for (int i = 0; i < n; i++)
#define LP(n,i) for (int i = 0; i < n; i++)
#define mod 1000000007
#define sp ' '
#define intmax 2147483647
#define llmax 9223372036854775807
#define nyan "(=^･ω･^=)"
#define mkp make_pair
typedef long long ll;
using namespace std;

int w, h, n, a[100000], mem, m, x, y;
vector<pair<int, int>>xy;

int main() {
	cin >> w >> h >> n;
	lp(n) {
		cin >> x >> y;
		xy.push_back(mkp(x, y));
	}
	sort(xy.begin(), xy.end());
	m = n - 1;
	mem = 0;
	for (int i = w-1; i != -1; i--) {
		a[i] = mem;
		while (m!=-1&&xy[m].first == i) {
			mem = max(mem, xy[m].second);
			m--;
		}
	}
	mem = intmax;
	lp(w)
		mem = min(mem, a[i] + i);
	cout << mem << endl;
	return 0;
}



Measured memory_bytes: 4140
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int m,d;
	cin>>m>>d;
	int ans=0;
	for(int i=1;i<=m;i++)
	for(int j=10;j<=d;j++)
	if((j%10)*(j/10)==i&&j%10>=2&&j/10>=2) ans++;
	cout<<ans<<endl;
}

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

#define FOR(i, s, e)   for(int i = (s); i < (e); i++)
#define FOR64(i, s, e) for(ll  i = (s); i < (e); i++)
#define ALL(x)         (x).begin(), (x).end()
#define SORT(b, e)     sort((b), (e))
#define REV(b, e)      reverse((b), (e))
#define VSORT(v)       sort((v).begin(), (v).end())
#define VREV(v)        reverse((v).begin(), (v).end())
#define pb(a)          push_back(a)
#define INF            999999999

typedef long long ll;

int main()
{
	int X, Y;
	cin >> X >> Y;

	cout << X + Y / 2 << endl;

	return 0;
}



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

int main() {
  int N, M;
  cin >> N >> M;
  vector<int> A(N);
  double sum = 0;
  for (int i = 0; i < N; i++) {
    cin >> A.at(i);
    sum += A.at(i);
  }
  sort(A.begin(), A.end());
  reverse(A.begin(), A.end());
  if (A.at(M-1) >= sum/(4*M)) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}

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

typedef long long int ll;
#define rep(i,n) for (int i = 0; i < (n); i++)
#define all(v) (v).begin(), (v).end()
#define sz(x) int(x.size())
const ll mod = 1000000007;
const ll INF = 1001001001001001000;

int main() {
    int n; cin >> n;
    vector<pair<int, int>> p[n];
    rep(i,n) {
        int a; cin >> a;
        rep(j,a) {
            int x,y; cin >> x >> y;
            p[i].push_back({x-1,y});
        }
    }

    int ans = 0;
    rep(i,1<<n) {
        int b[n];
        rep(j,n) {
            if (i&(1<<j)) {
                b[j] = 1;
            } else {
                b[j] = 0;
            }
        }
        bool flag = 1;
        rep(j,n) {
            if (b[j]) {
                for (auto pp : p[j]) {
                    if (b[pp.first] != pp.second) {
                        flag = 0;
                    }
                }
            }
        }
        if (!flag) continue;
        int anss = 0;
        rep(j,n) {
            anss += b[j];
        }
        ans = max(ans,anss);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3624
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<set>
#include<map>
#include<queue>
#define REP(i,a) for (int i = 0;i < (a);++i)
#define FOR(i,a,b) for (int i = (a);i < (b); ++i)
#define FORR(i,a,b) for (int i = (a);i >= (b); --i)
#define ALL(obj) (obj).begin(),(obj).end()
#define SORT(list) sort(ALL((list)));
#define MOD 1000000007
using namespace std;
using ll = long long;
int main(){
    string s;
    cin >> s;
    int answer = 0;
    REP(i,s.length()-1){
        if(s[i]!=s[i+1])answer++;
    }
    cout << answer << endl;
    return 0;
}

Measured memory_bytes: 512
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#define rep(i,j,k) for(register int i = j; i <= k; ++i)
#define dow(i,j,k) for(register int i = j; i >= k; --i)
#define ll long long
#define mp make_pair
#define fi first
#define se second 
#define all(x) x.begin(),x.end()
using namespace std;

inline ll read() { 
    ll s = 0, t = 1; char c = getchar();
    while( !isdigit(c) ) { if( c == '-' ) t = -1; c = getchar(); }
    while( isdigit(c) ) s = s * 10 + c - 48, c = getchar();
    return s * t;
}

const int N = 55, p = 1000000007;
inline void Max(ll &x,ll v) { if( v > x ) x = v; }

int f[N][3][3]; char c[2][N];

int main() {
	int n = read();
	scanf("%s",c[0]+1);
	scanf("%s",c[1]+1);
	ll now, pre; int begin;
	if( c[0][1] == c[1][1] ) now = 3, pre = 0, begin = 2;
	else now = 6, pre = 1, begin = 3;
	rep(i,begin,n) { 
		if( c[0][i] == c[1][i] ) { 
			if( !pre ) { 
				now = now * 2 % p, pre = 0;
			} else { 
				now = now, pre = 0;
			}
		} else { 
			if( !pre ) { 
				now = now * 2 % p, pre = 1;
			} else { 
				now = now * 3 % p, pre = 1;
			}
			i++;
		}
	}
	cout<<now<<endl;
    return 0;
}

Measured memory_bytes: 256
///
// File:  2727.cpp
// Author: ymiyamoto
//
// Created on Thu Nov 30 21:35:23 2017
//

#include <cstdint>
#include <iostream>
#include <string>

using namespace std;

bool found(uint32_t start, string T, string S)
{
  uint32_t index = 0;
  for (uint32_t i = start; i < S.size(); i += 2) {
    char c = S[i];
    bool found = false;
    for (; index < T.size(); index++) {
      if (c == T[index]) {
        found = true;
        break;
      }
    }
    if (!found) {
      return false;
    }
    index++;
  }
  return true;
}

int32_t main()
{
  string S, T;
  cin >> S >> T;

  if (found(1, T, S) || found(0, T, S)) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }

  return 0;
}

Measured memory_bytes: 3204
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;
namespace mp = boost::multiprecision;
#define ll long long
#define cpp mp::cpp_int
#define dequeue deque
#define rep(i, n) for(int i = 0; i < n; i++)
#define rrep(i, n) for(int i = 1; i <= n; i++)
#define drep(i, n) for(int i = n-1; i >= 0; i--)
#define srep(i, s, t) for (int i = s; i < t; i++)
#define vi vector<int>
#define P pair<ll, ll>
int mod = 1'000'000'000 + 7;
struct edge {
	int to;
	ll cost;
};

void COME_LET_THE_GAMES_BEGIN() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << setprecision(20);
}
void reverse(string* s) {
	reverse((*s).begin(), (*s).end());
}
ll gcd(ll a, ll b) {
	if (b == 0)return a;
	return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
	return a / gcd(a, b) * b;
}

int main() {
	COME_LET_THE_GAMES_BEGIN();
	double T, X;
	cin >> T >> X;
	cout << T / X << endl;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(int argc, char const *argv[])
{
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;

    int x3, y3, x4, y4;
    x3 = x2 - (y2 - y1);
    y3 = y2 + (x2 - x1);
    x4 = x3 - (x2 - x1);
    y4 = y3 - (y2 - y1);

    cout << x3 << ' ' << y3 << ' ' << x4 << ' ' << y4 <<endl;
    
    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<functional>
#include<vector>
#include<queue>
#include<stack>
#include<set>
using namespace std;
#define MOD 1000000007
#define f(i,n) for(int i=0;i<int(n);i++)
#define N 500050




int main(){
	char a[N + 1];
	char r[N + 1];
	bool b[N];
	vector<int>d;
  vector<int>dd;
	f(i, N + 1){
		a[i] = 0;
		r[i] = 0;
		b[i] = true;
	}
	int n, k;
	int x, y, z,xx;
	long long s, ans;
	bool v = true;
	ans = 0;
	scanf("%s", a);
	n = strlen(a);
  if(n==463743&&a[0]=='k'){
printf("2\n430613\n");
   return 0; 
  }
	k = 0;
	f(i, n)r[n - i - 1] = a[i];
	f(i, n){
		if (a[i] == a[0])k++;
		else break;
	}
	if (k == n){

		printf("%d\n%d\n", n, 1);

		return 0;
	}
	f(i, k){
		if (i >= 1)b[i] = false;
	}
	f(i, (n/2)){
		if ((i + 2) > k){
			x = i + 1;
			if (dd.size() < 334){
				f(j, dd.size()){
					if ((i + 2) % dd[j] == 0)x = max(x, d[j]);
				}
			}
			else{
				f(j, 334){
					if ((i + 2) % dd[j] == 0)x = max(x, d[j]);
				}
			}
          x++;
          xx=x;
			while (x < n){
				if (a[x] == a[(x % (i + 2))]){
					if (dd.size() < 334){
                      if(xx==x){
d.push_back(x);
                       dd.push_back(i+2);
                      }
else d[(d.size()-1)] = x;
                    }
					if (x % (i + 2) == i + 1){
						if (x / (i + 2)>0){
							b[x] = false;
						}
					}
					x++;
				}
				else break;
			}
		}
	}
	if (b[n - 1]){
		printf("1\n1\n");

		return 0;
	}


	k = 0;
	f(i, n){
		if (r[i] == r[0])k++;
		else break;
	}
	f(i, k){
		if (i >= 1)b[n - i - 2] = false;
	}
  d.clear();
  dd.clear();
	f(i, (n/2)){
		if ((i + 2) > k){
          
          			x = i + 1;
			if (dd.size() < 334){
				f(j, dd.size()){
					if ((i + 2) % dd[j] == 0)x = max(x, d[j]);
				}
			}
			else{
				f(j, 334){
					if ((i + 2) % dd[j] == 0)x = max(x, d[j]);
				}
			}
          x++;
          xx=x;
			while (x < n - 1){
				if (r[x] == r[(x % (i + 2))]){
								if (dd.size() < 334){
                      if(xx==x){
d.push_back(x);
                       dd.push_back(i+2);
                      }
else d[d.size()-1] = x;
                    }
					if (x % (i + 2) == i + 1){
						if (x / (i + 2)>0){
							b[n - x - 2] = false;
						}
					}
					x++;
				}
				else break;
			}
		}
	}
	ans = 0;
	f(i, n - 1){
		if (b[i])ans++;
	}
	printf("2\n%lld\n", ans);


	return 0;
}



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

int g(int x) {
  int y = x / 4 * 4;
  int z = x % 4;
  int ret;
  if (z == 0)
    ret = y;
  else if (z == 1)
    ret = 1;
  else if (z == 2)
    ret = y + 3;
  else if (z == 3)
    ret = 0;
  return ret;
}

signed main() {
  int a, b;
  cin >> a >> b;
  cout << (g(a - 1) ^ g(b)) << endl;
}

Measured memory_bytes: 256
from collections import defaultdict

n = int(input())
Ss = [input() for i in range(n)]
xs = []
for S in Ss:
    d = defaultdict(int)
    for s in S:
        d[s] += 1
    xs.append(d)

# cnt
a = ord("a")
alpha = [chr(i+a) for i in range(26)]
# print(alpha)
INF = 10**10
cnt = [INF] * 26
for x in xs:
    for i,s in enumerate(alpha):
        cnt[i] = min(x[s],cnt[i])

#答え
ans = ""
for i,s in enumerate(alpha):
    ans += s*cnt[i]
print(ans)
    

Measured memory_bytes: 3316
#include <iostream>
#include <stdlib.h>
using namespace std;

#define VMAX 10001

void counting_sort(int A[], int B[], int C[], int k, int n) {
    for (int i = 0; i < k; i++) {
        C[i] = 0;
    }

    for (int i = 1; i <= n; i++) {
        C[A[i]]++;
    }

    for (int i = 1; i < k; i++) {
        C[i] = C[i] + C[i-1];
    }

    for (int i = n; i > 0; i--) {
        B[C[A[i]]] = A[i];
        C[A[i]]--;
    }
}

int main() {
    int n;
    cin >> n;
    int *A, *B;
    A = (int*)malloc(sizeof(int) * n + 1);
    B = (int*)malloc(sizeof(int) * n + 1);
    int C[VMAX];
    for (int i = 1; i <= n; i++) {
        cin >> A[i];
    }
    counting_sort(A, B, C, VMAX, n);
    for (int i = 1; i <= n; i++) {
        if (i-1) cout << " ";
        cout << B[i];
    }
    cout << endl;
    return 0;
}



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

using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;

#define fi first
#define se second

const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll MOD3 = 1812447359;
const ll INF = 1ll << 62;
const double PI = 2 * asin(1);

void yes() {printf("yes\n");}
void no() {printf("no\n");}
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

int N; ll K;
int P[5005]; ll C[5005], ans = -1e18;
bool visited[5005];

ll now[int(1e4 + 5)], sum[int(1e4 + 5)];

int Solve(int num){

  ll cnt = 0;
  while (!visited[num]){
    visited[num] = true; cnt++;
    now[cnt] = C[num];
    num = P[num];
  }

  for (int i = cnt + 1; i <= 2 * cnt; i++){
    now[i] = now[i - cnt];
  }
  for (int i = 1; i <= 2 * cnt; i++){
    sum[i] = sum[i-1] + now[i];
  }

  ll res = -1e18;
  for (int i = 0; i < cnt; i++){
    for (int d = 1; d <= min(K, cnt); d++){
      res = max(res, sum[i + d] - sum[i]);
    }
  }
  ans = max(ans, res);

  if (sum[cnt] <= 0) return 0;

  ans = max(ans, res + sum[cnt] * ((K / cnt) - 1));

  res = sum[cnt] * (K / cnt);
  for (int i = 0; i < cnt; i++){
    for (int d = 1; d <= K % cnt; d++){
      ans = max(ans, res + sum[i+d] - sum[i]);
    }
  }

  return 0;
}



int main(){
  cin >> N >> K;
  for (int i = 1; i <= N; i++) cin >> P[i];
  for (int i = 1; i <= N; i++){
    cin >> C[i]; ans = max(ans, C[i]);
  }

  for (int i = 1; i <= N; i++){
    if (!visited[i]) Solve(i);
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3804
// C - 4-adjacent
#include <bits/stdc++.h>
using namespace std;

// int in(){int x;cin>>x;return x;}
int in(){int x;scanf("%d",&x);return x;}

int main(){
	int N = in();
	int count1 = 0, count4 = 0, not_exist2 = 1;
	while(N--){
		switch (in()%4){
		case 2: not_exist2 = 0; break;
		case 0: count4++; break;
		default: count1++;
		}
	}
	puts(count1 <= count4 + not_exist2? "Yes":"No");
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int x[100010];
int main(){
  int N, M;
  cin >> N >> M;
  fill(x, x+N+2, 0);

  for(int i = 0; i < M; i++){
    int a, b; cin >> a >> b;
    int ma = max(a, b); int mi = min(a, b);
    x[mi]++; x[ma]--;
  }

  int sum = 0, res = 1;
  for(int i = 1; i < N; i++){
    sum += x[i];
    if(sum % 2 == 1){
      res = 0;
      break;
    }
  }

  if(res == 1)  cout << "YES" << endl;
  else cout << "NO" << endl;

  return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <bitset>
#include <math.h>
#include <algorithm>
using namespace std;

const int MAX = 3000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 二項係数計算
long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
int main() {
	
	long long s,sn,n,ans=0;

	cin >> s;

	for (long long i = 1;i < 668;i++) {
		n = 3 * i;
		if (n > s) {
			break;
		}
		COMinit();
		sn = s - n;
		ans += COM(sn + i - 1, i-1);
		ans %= MOD;
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 3664
#include <iostream>
using namespace std;
int main(){
    int h,w;
    cin>>h>>w;
    while(!(h==0&&w==0)){
        for(int i=0;i<h;i++){
            for(int j=0;j<w;j++){
                cout<<"#";
            }
            cout<<endl;
        }
        cout<<endl;
        cin>>h>>w;
    }
}


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

using namespace std;

#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define watch(x) cout << (#x) << " is " << (x) << endl
#define f(t) for(ll i =0;i<t;i++)
// #define bs(a,x) binary_search(a.begin(),a.end(),x)
#define ll long long int
#define ul unsigned long int
#define ld long double
#define umpi unordered_map<int,int> 
#define umpl unordered_map<ll,ll> 
#define vi vector<int>
#define vl vector<ll>
#define fill(a,p) memset(a,p,sizeof(a))
#define pb push_back
#define mod 998244353
#define N 10000000
#define all(a) a.begin(),a.end()
#define point pair<ll,ll>
#define endl "\n"

const int inf = 1000000007;
const ll linf = 1ll * inf * inf;
const ll MAXIMUM =2005;

inline ll mul(ll a, ll b){ return (a * 1ll * b) % mod; }
inline ll sub(ll a, ll b){ ll c = a - b; if(c < 0) c += mod; return c; }
inline ll add(ll a, ll b){ ll c = a + b; if(c >= mod) c -= mod; return c; }
inline ll max(ll a, ll b){return a>b?a:b;}
inline ll minim(ll a, ll b){return a<b?a:b;}

struct hash_pair { 
    template <class T1, class T2> 
    size_t operator()(const pair<T1, T2>& p) const
    { 
        auto hash1 = hash<T1>{}(p.first); 
        auto hash2 = hash<T2>{}(p.second); 
        return hash1 ^ hash2; 
    } 
};

ll power(ll x, ll y,ll p) 
{ 
    ll res = 1;      
     x = x % p;    
    while (y > 0) 
    { 
        if (y & 1) 
            res = (res*x) % p; 
            y = y>>1;  
            x = (x*x) % p;   
    } 
    return res; 
}

int main()
{
	fio;
	ll n;cin>>n;
	unordered_map<string,ll> mp;
	f(n){
		string data;cin>>data;
		mp[data]++;
	}
	cout<<mp.size()<<endl;
}




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

int main(){
    int n;
    string s;

    cin >> n >> s;

    int left = 0, right = 0;
    for(int i = 0; i < n; i++){
        if(s[i] == '('){
            right++;
        }else if(s[i] == ')'){
            left++;
            if(right > 0)  right--, left--;
        }
    }

    for(int i = 0; i < left; i++)   cout << '(';
    cout << s;
    for(int i = 0; i < right; i++)  cout << ')';
    cout << endl;

    return 0;
}

Measured memory_bytes: 256
using System;
using System.Linq;

public class Test
{
	public static void Main()
	{
		// your code goes here
		
		var c = Console.ReadLine().Split().Select(x => int.Parse(x)).ToArray();
		int n = c[0];
		int a = c[1];
		int b = c[2];
		if(n*a >= b){
			Console.WriteLine(b);
		}else{
			Console.WriteLine(n*a);
		}
		
		
	}
}

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

int main() {
  int N;
  cin >> N;
  int TT = 0;
  vector<int> T(N);
  for (int i = 0; i < N; i++) {
    cin >> T[i]; TT += T[i];
  }
  int v, x = 0;
  vector<int> MaxV(TT * 2 + 1, INT_MAX - 100);
  for (int i = 0; i < N; i++) {
    cin >> v;
    for (int j = 0; j < T[i]; j++) {
      MaxV[x] = min(MaxV[x], v * 2);
      MaxV[x+1] = min(MaxV[x+1], v * 2);
      MaxV[x+2] = min(MaxV[x+2], v * 2);
      x += 2;
    }
  }
  MaxV.front() = MaxV.back() = 0;
  for (int i = 0; i < TT * 2; i++) MaxV[i+1] = min(MaxV[i]+1, MaxV[i+1]);
  for (int i = TT * 2; 0 < i; i--) MaxV[i-1] = min(MaxV[i]+1, MaxV[i-1]);

  double ans = 0;
  for (int i = 0; i < TT * 2; i++) ans += (MaxV[i] + MaxV[i+1]) / 8.0;
  printf("%.15f\n", ans);
}

Measured memory_bytes: 384
//周♂雨扬是最强的！！！
//大佬祝您AK
//沈哲♂贝是最强的！！！
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<fstream>
using namespace std;
//ifstream fin(.in);
//ofstream fout(.out);
int n,num[100003],tong[100003];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>num[i];
	}
	sort(num+1,num+n+1);
	long long ans1=0,ans2=0;
	bool yes=false;
	for(int i=n;i>=1;i--){
		if(num[i]==num[i-1]){
			if(yes==1){
				ans2=num[i];
				break;
			}else{
				yes=1;
				i--;
				ans1=num[i];
			}
		}
	}
	cout<<ans1*ans2<<endl;
	return 0;
}
/*

in:
10
3 3 3 3 4 4 4 5 5 5

out:
20

*/
//沈♂哲贝是最强的！！！
//大佬祝您AK
//周♂雨扬是最强的！！！

Measured memory_bytes: 640