akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <iomanip>
#include <stack>
#include <list>
#include <unordered_map>
using namespace std;


vector<string> split(const string &s, char delim) {
    vector<string> elems;
    string item;
    for (char ch: s) {
        if (ch == delim) {
            if (!item.empty())
                elems.push_back(item);
            item.clear();
        }
        else {
            item += ch;
        }
    }
    if (!item.empty())
        elems.push_back(item);
    return elems;
}

bool compare_by_b(tuple<int, string, int> a, tuple<int, string, int> b) {
    if(get<2>(a) != get<2>(b)){
        return get<2>(a) > get<2>(b);
    }
}

bool compare_by_string(tuple<int, string, int> a, tuple<int, string, int> b) {
    if(get<1>(a) != get<1>(b)){
        return get<1>(a) < get<1>(b);
    }else{
      	return get<2>(a) > get<2>(b);
    }
}


int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N;
  	cin >> N;
  	int idx = 0;
  	int W[N];
  	int sum = 0;
  	while(cin >> W[idx])
    {
      sum += W[idx];
      idx++;
    }
  	int min = sum;
  	int tmp = 0;
  	cerr << sum << endl;
  	for(int i=0;i<N;i++)
    {
      tmp += W[i];
      cerr << abs(sum - 2*tmp) << endl;
      if(abs(sum - 2*tmp) < min) min = abs(sum - 2*tmp);
    }
  	cout << min << endl;
  	return 0;
}


Measured memory_bytes: 256
# coding: utf-8
# Your code here!
w,h,x,y=map(int,input().split())
#print(min(max(x*h,(w-x)*h),max(y*w,(h-y)*w)))
if w==x+x and h==y+y:
    print(float(w)*float(h)/2,1)
else:
    print(float(w)*float(h)/2,0)



Measured memory_bytes: 2940
#include<iostream>
#include<cctype>
#include<cstring>
using namespace std;
int main()
{
	char line[20];
	int x, y, i;
	x = 0;
	y = 0;
	cin >> line;
	if( strlen(line) >= 6 )
	{
		x = strlen(line);
		for ( i = 0; i < x; i++)
		{
			if( isdigit(line[i]) != 0)
			{
				y++;
			}
		}
		if( y != 0)
		{
			y = 0;
			for ( i = 0; i < x; i++)
			{
				if( isupper(line[i]) != 0)
				{
					y++;
				}
			}
			if( y != 0)
			{
				y = 0;
				for ( i = 0; i < x; i++)
				{
					if( islower(line[i]) != 0)
					{
						y++;
					}
				}
				if( y != 0)
				{
					cout << "VALID" << endl;
				}
				else
				{
					goto OUT;
				}
			}
			else
			{
				goto OUT;
			}
			
		}
		else
		{
			goto OUT;
		}
	}
	else
	{
		OUT:
			cout << "INVALID" << endl;
	}

}

Measured memory_bytes: 1140
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <queue>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <complex>
#include <cstdint>
#include <tuple>
#include <numeric>
#define M_PI       3.14159265358979323846


using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define MT make_tuple
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define FILL(a, x) memset(a, x, sizeof(a))

//repetition
//------------------------------------------
#define FOR(i,s,n) for(int i=s;i<(int)n;++i)
#define REP(i,n) FOR(i,0,n)
#define MOD 1000000007

int v[55];
LL dp[105][55][55];

int main() {
	int n, r;
	scanf("%d%d", &n, &r);
	REP(i, n)scanf("%d", &v[i]);
	vector<vector<vector<LL>>> dp(r + 2, vector<vector<LL>>(n+1, vector<LL>(n+1, -2e18)));
	dp[0][0][n] = 0;
	REP(i, r) {
		REP(j, n+1) {
			FOR(k, j+1, n+1) {
				dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k]);
				dp[i + 1][j + 1][k] = max(dp[i + 1][j + 1][k], dp[i][j][k] + v[j]);
				dp[i + 1][j][k - 1] = max(dp[i + 1][j][k - 1], dp[i][j][k] + v[k-1]);
				dp[i + 2][j + 1][k] = max(dp[i + 2][j + 1][k], dp[i][j][k]);
				dp[i + 2][j][k - 1] = max(dp[i + 2][j][k - 1], dp[i][j][k]);
			}
		}
	}
	LL ret = 0;
	REP(i, r + 1) {
		REP(j, n + 1) {
			REP(k, n + 1) {
				ret = max(ret, dp[i][j][k]);
			}
		}
	}
	cout << ret << endl;
	return 0;
}


Measured memory_bytes: 2560
#include <stdio.h>
#include <stdlib.h>
#define int long long
#define inf (int)(1e18)

int min(int a, int b){
	return a <= b ? a : b;
}

signed main(){
	int L, i;
	scanf("%lld", &L);
	int *A = (int *)malloc(sizeof(int) * (L + 1));
	int *B = (int *)malloc(sizeof(int) * (L + 1));
	int *C = (int *)malloc(sizeof(int) * (L + 1));
	int *S = (int *)malloc(sizeof(int) * (L + 1));
	S[0] = 0;
	int f = 1;
	for(i = 1; i <= L; i++){
		scanf("%lld", &A[i]);
		if(A[i] == 0){
			B[i] = 2;
		}
		else{
			f = 0;
			B[i] = A[i] % 2;
		}
		if(A[i] % 2 == 0){
			C[i] = 1;
		}
		else{
			C[i] = 0;
		}
		S[i] = S[i - 1] + A[i];
	}
	if(f == 1){
		printf("0\n");
		return 0;
	}
	int *dp1 = (int *)malloc(sizeof(int) * (L + 1));
	int *dp2 = (int *)malloc(sizeof(int) * (L + 1));
	int *dp3 = (int *)malloc(sizeof(int) * (L + 1));
	dp1[0] = inf;
	dp2[0] = inf;
	dp3[0] = inf;
	int ans = inf;
	for(i = 1; i <= L; i++){
		dp1[i] = min(S[i - 1], dp1[i - 1]) + B[i];
		dp2[i] = min(S[i - 1], min(dp1[i - 1], dp2[i - 1])) + C[i];
		dp3[i] = min(min(S[i - 1], dp1[i - 1]), min(dp2[i - 1], dp3[i - 1])) + B[i];
		ans = min(ans, min(min(dp1[i], dp2[i]), dp3[i]) + S[L] - S[i]);
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 12928
#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 3 * 1e3 + 5;

int n;
long long a[MAXN];
long long z;

void read_input()
{
    scanf("%d", &n);

    for(int i = 0; i < n; i++)
    {
        scanf("%lld", &a[i]);
        z += a[i];
    }
}

pair<long long,long long> T[MAXN][MAXN][2];

pair <long long, long long> rec(int l, int r, int t)
{
    if(l == r)
    {
        if(t == 0) return {a[l], 0};
        if(t == 1) return {0, a[l]};
    }
    if(T[l][r][t].first != 0 || T[l][r][t].second != 0)
    {
        return T[l][r][t];
    }
    long long f;
    if(t == 0) f = rec(l, r - 1, t ^ 1).first + a[r];
    else f = rec(l, r - 1, t ^ 1).second + a[r];
    long long s;
    if(t == 0) s = rec(l + 1, r, t ^ 1).first + a[l];
    else s = rec(l + 1, r, t ^ 1).second + a[l];

    if(t == 1)
    {
        if(f > s)
        {
            return T[l][r][t] = {rec(l, r - 1, t ^ 1).first, f};
        }
        else
        {
            return T[l][r][t] = {rec(l + 1, r, t ^ 1).first, s};
        }
    }
    else
    {
        if(f > s)
        {
            return T[l][r][t] = {f, rec(l, r - 1, t ^ 1).second};
        }
        else
        {
            return T[l][r][t] = {s, rec(l + 1, r, t ^ 1).second};
        }
    }
}

void solve()
{
    long long X = rec(0, n - 1, 0).first;
    //printf("%lld\n", X);
    printf("%lld\n", 2 * X - z);
}

int main()
{
    read_input();
    solve();

    return 0;
}


Measured memory_bytes: 218624
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAXN 100005
int n,a[MAXN],sum;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		if(a[i]%2) sum++;
	}
	if(sum%2) printf("NO\n");
	else printf("YES\n");
	return 0;
}

Measured memory_bytes: 512
#include <stdio.h>
int main(){
int a,b;
char op;

while(1){
scanf("%d %c %d",&a,&op,&b);
if(op=='?')break;
else if(op=='+'){
printf("%d\n",a+b);
}else if(op=='-'){
printf("%d\n",a-b);
}else if(op=='*'){
printf("%d\n",a*b);
}else if(op=='/'){
printf("%d\n",a/b);
}
}
return 0;
}



Measured memory_bytes: 2112
#include <bits/stdc++.h>
using namespace std;
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
typedef pair<int, int> Pint;
typedef pair<int64_t, int64_t> Pll;
  
int main() {
    int N, M, sum = 0;
    cin >> N;
    vector<int> T(N);
    for (int i = 0; i < N; i++) {
        cin >> T.at(i);
        sum += T.at(i);
    }
    cin >> M;
    vector<Pint> PX(M);
    for (int i = 0; i < M; i++) {
        cin >> PX.at(i).first >> PX.at(i).second;
    }
    for (int i = 0; i < M; i++) {
        cout << sum - T.at(PX.at(i).first - 1) + PX.at(i).second << endl;
    }
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
accA = [0]

for Ai in A:
    accA.append(accA[-1]+Ai)

accB = [0]

for Bi in B:
    accB.append(accB[-1]+Bi)

ans = 0
j = M

for i in range(N+1):
    if accA[i]>K:
        break
    
    while accA[i]+accB[j]>K:
        j -= 1
    
    ans = max(ans, i+j)

print(ans)

Measured memory_bytes: 134436
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define R cin>>
#define Z class
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1e9+7,MAXL=1LL<<61,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<int,int> P;
typedef pair<int,P> PP;
const int N=60;
int d[N][N][N];
void Main() {
  memset(d,-1,sizeof(d));
  int x,y,z;
  cin >> x >> y >> z;
  d[x][y][z]=0;
  queue<PP> que;
  que.push(PP(x,P(y,z)));
  while(!que.empty()) {
    PP p=que.front();que.pop();
    int xx=p.F,yy=p.S.F,zz=p.S.S;
    if(xx==yy&&xx==zz) {
      pr(d[xx][yy][zz]);
      return;
    }
    {
      x=xx+1,y=yy+1,z=zz;
      if(x<N&&y<N&&z<N&&d[x][y][z]==-1) {
        d[x][y][z]=d[xx][yy][zz]+1;
        que.push(PP(x,P(y,z)));
      }
    }
    {
      x=xx+1,y=yy,z=zz+1;
      if(x<N&&y<N&&z<N&&d[x][y][z]==-1) {
        d[x][y][z]=d[xx][yy][zz]+1;
        que.push(PP(x,P(y,z)));
      }
    }
    {
      x=xx,y=yy+1,z=zz+1;
      if(x<N&&y<N&&z<N&&d[x][y][z]==-1) {
        d[x][y][z]=d[xx][yy][zz]+1;
        que.push(PP(x,P(y,z)));
      }
    }
    {
      x=xx+2,y=yy,z=zz;
      if(x<N&&y<N&&z<N&&d[x][y][z]==-1) {
        d[x][y][z]=d[xx][yy][zz]+1;
        que.push(PP(x,P(y,z)));
      }
    }
    {
      x=xx,y=yy+2,z=zz;
      if(x<N&&y<N&&z<N&&d[x][y][z]==-1) {
        d[x][y][z]=d[xx][yy][zz]+1;
        que.push(PP(x,P(y,z)));
      }
    }
    {
      x=xx,y=yy,z=zz+2;
      if(x<N&&y<N&&z<N&&d[x][y][z]==-1) {
        d[x][y][z]=d[xx][yy][zz]+1;
        que.push(PP(x,P(y,z)));
      }
    }
  }
}

int main(){ios::sync_with_stdio(0);cin.tie(0);Main();return 0;}


Measured memory_bytes: 1152
#include <cmath>
#include <iostream>

using namespace std;
using ll = long long;

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

int main() {
  int a, b, h, m;
  cin >> a >> b >> h >> m;

  double t = abs(
      ((2 * M_PI * h / 12.0 + M_PI * m / 60.0 / 6.0) - 2 * M_PI * m / 60.0));

  double ans = sqrt((double)a * a + (double)b * b - 2 * a * b * cos(t));

  // ans = sqrt(25.0 - 8 * sqrt(3));

  printf("%.15f\n", ans);
  return 0;
}


Measured memory_bytes: 4192
#include<bits/stdc++.h>
using namespace std;
#define pfi(a) printf("%d",a);
#define pfl(a) printf("%lld ",a);
#define pfin(a) printf("%d\n",a);
#define pfln(a) printf("%lld\n",a);
#define sfi(a) scanf("%d",&a);
#define sfl(a) scanf("%lld",&a);
#define pb push_back
#define f first
#define s second
#define vi vector<int>
#define vl vector<long long>
#define vs vector<string>
#define watch(x) cout << (#x) << " is " << (x) << endl
#define d0(x) cout<<(x)<<" "
#define d1(x) cout<<(x)<<endl
#define d2(x,y) cout<<(x)<<" "<<(y)<<endl
#define d3(x,y,z) cout<<(x)<<" "<<(y)<<" "<<(z)<<endl
#define d4(a,b,c,d) cout<<(a)<<" "<<(b)<<" "<<(c)<<" "<<(d)<<endl
#define d5(a,b,c,d,e) cout<<(a)<<" "<<(b)<<" "<<(c)<<" "<<(d)<<" "<<(e)<<endl
#define fo(i,a,b) for(int i=a;i<b;i++)
#define all(c) (c).begin(),(c).end()
#define ll long long
const int M=1e9+7;
#define endl "\n"
const double pyi=3.14159265358979323846;

// vector<int> factors(int n)
// {
// 	vector<int> ans;
// 	int j=2;
// 	if(n%2==0) ans.push_back(2);
// 	while(n%2==0)
// 	{
//         n=n/2;
// 	}
// 	for(int j=3;j<=n/2;j=j+2)
// 	{
// 		if(n%j==0) ans.push_back(j);
// 		while(n%j==0) n=n/j;
// 	}
// 	if(n!=1) ans.push_back(n);
// 	return(ans);
// }



int main() 
{ 
    int n; cin>>n;
    int arr[n];
    for(int i=0;i<n;i++) cin>>arr[i];
    sort(arr,arr+n);
    bool temp[1000006]={0};
    int ans=0;
    unordered_set<int> stt;
    for(int i=0;i<n;i++)
    {
    	int val=arr[i];
    	if(i<n-1 && arr[i]!=arr[i+1])
    	{
    		if(temp[val]==0) ans++;
    	}
    	if(i==n-1 && temp[val]==0) ans++;
    	if(stt.find(val)!=stt.end()) continue;
    	stt.insert(val);
    	for(int j=val;j<1000006;j=j+val) temp[j]=1;
    }
    cout<<ans<<endl;
    
    
    return(0);
}





Measured memory_bytes: 13116
#include<bits/stdc++.h>                                                                                                                
using namespace std;
double xa[100][100];
int main(){
    double n,d,x=0;
    int ts=0,cnt=0;
    cin >> n >> d;
    for(int i=0;i<n;i++){
        for(int j=0;j<d;j++){
            cin >> xa[i][j] ;
    }   
    }   
    for(int i=0;i<n-1;i++){
        for(int j=i+1;j<n;j++){
            x=0;
            for(int k=0;k<d;k++){
               x += pow(abs(xa[i][k]-xa[j][k]),2);  
            }
            x = sqrt(x);
            if(x == (int)x) cnt++;
        }
    }   
    cout << cnt << '\n';
return 0;   

}


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

int main() {
  int a, b;
  char op;
  
  cin >> a >> op >> b;
  
  if (op == '+') {
    cout << a + b << endl;
  }
  if (op == '-') {
    cout << a - b << endl;
  }
}


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

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

  int p[5000];
  for(int i=0; i<N; i++){
    cin>>p[i];
  }

  int min_sum=20000;

  for(int i=0; i<=p[0]; i++){
    int q[5000];
    for(int j=0; j<N; j++){
      q[j]=p[j];
    }

    int sum=i;
    q[0]-=i;

    for(int j=0; j<=N-2; j++){
      if(q[j]<=0)
        continue;

      sum+=q[j]*2;
      q[j+1]-=q[j];
    }

    if(q[N-1]>0){
      sum+=q[N-1];
    }

    min_sum=min(min_sum,sum);
  }

  cout<<min_sum<<endl;
  return 0;
}

Measured memory_bytes: 3120
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <string>
#include <stdio.h>
#include <cmath>
#include <limits.h>
using namespace std;

typedef long long ll;

#define min(a, b) (((a) < (b))? (a):(b))
#define max(a, b) (((a) > (b))? (a):(b))
#define REP(i, a, n) for(int i=(a); i<(n); ++i)
#define rep(i, n) REP(i, 0, (n))
#define square(a) (a)*(a)
#define pb push_back


string s;
int c;
int main(void) {
    cin >> s;
    c = s.length();
    cout << s[0] << c-2 << s[c-1] << endl;
}

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

signed main() {
    int n;
    cin>>n;
    map<string,int> M;
    string temp;
    for(int i=0;i<n;i++)
    {
        cin>>temp;
        M[temp]++;
    }
    cout<<"AC x "<<M["AC"]<<endl;
    cout<<"WA x "<<M["WA"]<<endl;
    cout<<"TLE x "<<M["TLE"]<<endl;
    cout<<"RE x "<<M["RE"]<<endl;
    return 0;
}

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

int main(){
  int N;
  cin>>N;
  for(int i=0; i<N; i++){
    int A;
    cin>>A;
    if(A%2==0&&(A%3!=0&&A%5!=0)){
      cout<<"DENIED"<<endl;
      return 0;
    }
  }
  cout<<"APPROVED"<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
int main(void)
{
    char a;
    scanf("%c", &a);
    if ('a' <= a && a <= 'z')
    {
        printf("a\n");
    }
    else
    {
        printf("A\n");
    }
    return 0;
}

Measured memory_bytes: 1584
using System;

namespace ITP1_4_C
{
    class Program
    {
        static void Main(string[] args)
        {
            while (true)
            {
                string str = Console.ReadLine();
                string[] parseStr = str.Split((char[])null);
                int a, b;
            
                a = int.Parse(parseStr[0]);
                b = int.Parse(parseStr[2]);

                if (parseStr[1] == "?" || a < 0 || a > 20000 || b < 0 || b > 20000)
                {
                    Environment.Exit(0);
                }

                switch(parseStr[1])
                {
                    case "+":
                        Console.WriteLine("{0}", a + b);
                        break;
                    case "-":
                        Console.WriteLine("{0}", a - b);
                        break;
                    case "*":
                        Console.WriteLine("{0}", a * b);
                        break;
                    case "/":
                        Console.WriteLine("{0}", a / b);
                        break;
                }
            }
        }
    }
}


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

#define rep(i,m,n) for(int (i)=(int)(m);i<(int)(n);i++)
#define rep2(i,m,n) for(int (i)=(int)(n)-1;i>=(int)(m);i--)
#define REP(i,n) rep(i,0,n)
#define REP2(i,n) rep2(i,0,n)
#define FOR(i,c) for(decltype((c).begin())i=(c).begin();i!=(c).end();++i)
#define all(hoge) (hoge).begin(),(hoge).end()
#define en '\n'
using ll = long long;
using ull = unsigned long long;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;
typedef pair<ll, ll> P;
constexpr long long INF = 1LL << 60;
constexpr int INF_INT = 1 << 25;
//constexpr long long MOD = (ll) 1e9 + 7;
constexpr long long MOD = 998244353LL;
typedef vector<ll> Array;
typedef vector<Array> Matrix;


template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

struct Edge {
	ll to, cap, rev;
	Edge(ll _to, ll _cap, ll _rev) {
	to = _to; cap = _cap; rev = _rev;
	}
};
using Edges = vector<Edge>;
using Graph = vector<Edges>;

void add_edge(Graph& G, ll from, ll to, ll cap, bool revFlag, ll revCap) {
	G[from].push_back(Edge(to, cap, (ll)G[to].size()));
	if (revFlag)G[to].push_back(Edge(from, revCap, (ll)G[from].size() - 1));
}

void solve(){
    ll n,m;
    cin>>n>>m;
    Graph g(n);
    REP(i,m){
        ll a,b;
        cin>>a>>b;
        a--;b--;
        add_edge(g,a,b,1,true,1);
    }

    ll q;
    cin>>q;
    Array v(q),d(q),c(q);
    REP(i,q){ 
        cin>>v[i]>>d[i]>>c[i];
        v[i]--;
    }

    P id={-1,0};
    vvec<P> dp(n+1,vec<P>(20,id));

    REP2(i,q){
        if(dp[v[i]][d[i]]!=id) continue;
        dp[v[i]][d[i]]={i,c[i]};
        queue<P> que;
        que.push({v[i],d[i]});
        while(que.size()){
            ll vv=que.front().first;
            ll dd=que.front().second;
            que.pop();
            if(dd==0) continue;
            for(auto e:g[vv]){
                if(dp[e.to][dd-1]!=id) continue;
                dp[e.to][dd-1] = {i,c[i]};
                que.push({e.to,dd-1});
            }
        }
    }

    REP(i,n){
        P ans=id;
        REP(dd,11){
            chmax(ans,dp[i][dd]);
            //if(dp[i][dd]!=id)cout<<dd<<" "<<dp[i][dd].first<<" "<<dp[i][dd].second<<en;
        }
        cout<<ans.second<<en;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    solve();
    //ll t;cin>>t;REP(i,t) solve();

    return 0;
}

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

int main()
{
    int x;
    std::string s;
    std::cin >> x >> s;
    if(x%2) std::cout << "No" << "\n";
    else if (x = x/2, s.compare(0, x, s, x, x) == 0)
    {
        std::cout << "Yes" << "\n";
    }
    else std::cout << "No" << "\n";
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i = j;i<k;i++)
int H,W;
char m[102][102];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
void DFS(int x,int y,char c){
  if(m[x][y]!=c)return;
  m[x][y]='.';
  rep(i,0,4){
    DFS(x+dx[i],y+dy[i],c);
  }
}
int main(){
  cin >>H>>W;
  while(H!=0){
    int count =0;
    rep(i,0,102)rep(j,0,102)m[i][j]='.';
    rep(i,1,H+1)rep(j,1,W+1)cin >>m[i][j];
    rep(i,1,H+1)rep(j,1,W+1){
      if(m[i][j]!='.'){
        DFS(i,j,m[i][j]);
        count++;
      }
    }
    cout << count<<endl;
    cin >> H>>W;
  }
  return 0;
}



Measured memory_bytes: 3460
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
typedef double ld;
typedef complex<ld> Point;
const ll INF = mod * mod;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
const ld eps = 1e-6;
const ld pi = acos(-1.0);
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;

int dx[8] = { 1,1,1,0,-1,-1,-1,0 };
int dy[8] = { 1,0,-1,-1,-1,0,1,1 };

int n;
map<P, bool> used;
//map<P, int> memo;
char mp[5][5];

vector<P> nexc(int loc, int s) {
	//cout << loc << " " << s << endl;
	//if (s == 0)return 0;
	vector<P> ret;
	//if (used[{loc, s}])return memo[{loc, s}];
	//used[{loc, s}] = true;
	vector<vector<bool>> g(n);
	rep(i, n) {
		g[i].resize(n);
		rep(j, n) {
			int z = i * n + j;
			if (s&(1 << z))g[i][j] = true;
			else g[i][j] = false;
		}
	}
	int x = loc / n, y = loc % n;
	rep(k, 8) {
		int nx = x + dx[k], ny = y + dy[k];
		if (nx < 0 || ny < 0 || nx >= n || ny >= n)continue;
		if (g[nx][ny])continue;
		int nloc = nx * n + ny;
		int nex = 0;
		rep(i, n) {
			rep(j, n) {
				int z = i * n + j;
				if (z == nloc)continue;
				
				int cnt = 0;
				rep(l, 8) {
					int sx = i + dx[l], sy = j + dy[l];
					if (sx < 0 || sy < 0 || sx >= n || sy >= n)continue;
					if (g[sx][sy]||sx*n+sy==nloc)cnt++;
				}
				if (g[i][j]) {
					if (cnt == 3 || cnt == 2)nex += (1 << z);
				}
				else {
					if (cnt == 3)nex += (1 << z);
				}
			}
		}
		if (!used[{nloc, nex}]) {
			used[{nloc, nex}] = true;
			ret.push_back({ nloc,nex });
		}
	}
	return ret;
}

void solve(){
	used.clear(); 
	//memo.clear();
	int s = 0;
	int x = 0;
	rep(i, n) {
		rep(j, n) {
			cin >> mp[i][j];
			int z = i * n + j;
			if (mp[i][j] == '#') {
				s += (1 << z);
			}
			else if (mp[i][j] == '@') {
				x = z;
			}
		}
	}
	queue<P> q; q.push({ x,s }); used[{x, s}] = true;
	int tmp = 0;
	while (!q.empty()) {
		int len = q.size();
		rep(aa, len) {
			P p = q.front(); q.pop();
			x = p.first, s = p.second;
			if (s == 0) {
				cout << tmp << endl; return;
			}
			vector<P> c = nexc(x, s);
			rep(i, c.size())q.push(c[i]);
		}
		tmp++;
	}
	cout << -1 << endl;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	while (cin >> n, n) {
		solve();
	}
	//stop
		return 0;
}


Measured memory_bytes: 4292
// https://atcoder.jp/contests/agc024/tasks/agc024_b
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
#define FOR(i, a, b) for (int i = (a); i < (int)(b); ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, len = 1, maxv = 0;
    cin >> n;
    vector<int> v(n), rev(n);
    REP(i, n) {
        int t;
        cin >> t;
        v[i] = t - 1;
    }
    REP(i, n) rev[v[i]] = i;
    REP(i, n - 1) {
        if (rev[i] < rev[i + 1]) {
            len++;
        } else {
            maxv = max(maxv, len);
            len = 1;
        }
    }
    maxv = max(maxv, len);
    cout << n - maxv << endl;
    return 0;
}


Measured memory_bytes: 1792
#define _USE_MATH_DEFINES
#define INF 0x3f3f3f3f

#include <iostream>
#include <cstdio>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>
#include <cctype>
#include <utility>
  
using namespace std;
  
typedef long long ll;
typedef pair <int,int> P;
typedef pair <int,P> PP;
  
static const double EPS = 1e-8;
  
static const int tx[] = {0,1,0,-1};
static const int ty[] = {-1,0,1,0};

class Edge {
public:
  int to;
  int weight;
  Edge(int to, int weight)
    : to(to), weight(weight) {}
};

class State {
public:
  int pos;
  int cost;
  int visited;
  State(int pos, int cost)
    : pos(pos), cost(cost), visited(0) {}
  State(int pos, int cost, int visited)
    : pos(pos), cost(cost), visited(visited) {}
  bool operator<(const State& s) const {
    return cost < s.cost;
  }
  bool operator>(const State& s) const {
    return cost > s.cost;
  }
};

int dp[1001][1<<12];

int main(){
  int total_nodes;
  int total_edges;
  int total_lost_posts;
  int starting_point;
  while(~scanf("%d %d %d %d",
               &total_nodes,
               &total_edges,
               &total_lost_posts,
               &starting_point)){
    starting_point--;
    memset(dp,0x3f,sizeof(dp));
    vector<Edge> edges[1001];
    for(int edge_i = 0; edge_i < total_edges; edge_i++){
      int from,to,weight;
      scanf("%d %d %d",&from,&to,&weight);
      from--; to--;
      edges[from].push_back(Edge(to,weight));
      edges[to].push_back(Edge(from,weight));
    }

    bool is_letter[1001] = {};
    bool is_post[1001] = {};
    int letter2idx[1001] = {};
    int post2idx[1001] = {};
    int post2letter[1001] = {};
    for(int post_i = 0; post_i < total_lost_posts; post_i++){
      int from,to;
      scanf("%d %d",&from,&to);
      from--; to--;
      is_letter[from] = true;
      is_post[to] = true;
      letter2idx[from] = post_i;
      post2idx[to] = total_lost_posts +  post_i;
      post2letter[to] = from;
    }

    priority_queue<State,vector<State>,greater<State> > que;
    que.push(State(starting_point,0));
    dp[starting_point][0] = 0;
    while(!que.empty()){
      State s = que.top();
      que.pop();
      for(int i = 0; i < edges[s.pos].size(); i++){
        int to = edges[s.pos][i].to;
        int weight = edges[s.pos][i].weight;
        int next_visited = s.visited;
        if(is_letter[to]){
          next_visited |= (1<<letter2idx[to]);
        }
        if(is_post[to] && (s.visited & (1<<letter2idx[post2letter[to]]))){
          next_visited |= (1<<post2idx[to]);
        }
        if(dp[to][next_visited] <= s.cost + weight) continue;
        dp[to][next_visited] = s.cost + weight;
        que.push(State(to,s.cost + weight,next_visited));
      }
    }

    int res = INF;
    for(int node_i = 0; node_i < total_nodes; node_i++){
      res = min(res,dp[node_i][(1<<(total_lost_posts*2)) - 1]);
    }
    
    if(res == INF){
      printf("Cannot deliver\n");
    }
    else{
      printf("%d\n",res);
    }
  }
}

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

int main() {
  string S;
  cin>>S;
  if(S=="RRR"){cout<<3<<endl;}
  else if(S=="RRS"||S=="SRR"){cout<<2<<endl;}
  else if(S=="RSS"||S=="SRS"||S=="SSR"||S=="RSR"){cout<<1<<endl;}
  else{cout<<0<<endl;}
}

Measured memory_bytes: 3580
#include<stdio.h>
int main(void){
	int n,q;
    	scanf("%d %d\n",&n,&q);
    	char s[n];
    	int l[2][q];
    	scanf("%s",s);
    	int i=0;
   	int h[n];
    	h[0]=0;
    	for(i=0;i<n-1;i++){
    		if(s[i]=='A'&&s[i+1]=='C') h[i+1] = 1+h[i];
    		else h[i+1]=h[i];
    	}
     	for(i=0;i<q;i++){
    		scanf("%d %d\n",&l[0][i],&l[1][i]);
    	}
    	for(i=0;i<q;i++){
    		printf("%d\n",h[l[1][i]-1]-h[l[0][i]-1]);
    	}
    	return 0;
}

Measured memory_bytes: 2048
#include<stdio.h>
int main(){
  int n[3], work, i, j;
  scanf("%d %d %d", &n[0], &n[1], &n[2]);
  for(i = 0;i < 2;i++){
    for(j = i;j < 3;j++){
      if(n[i] > n[j]){
        work = n[i];
        n[i] = n[j];
        n[j] = work;
      }
    }
  }
  printf("%d %d %d\n", n[0], n[1], n[2]);
  return 0;
}


Measured memory_bytes: 2100
open Printf
open Scanf

module Wf = struct
  type cost = C of int | Inf

  type t = int * cost array array

  let make n : t = let ar = Array.make_matrix n n Inf in
                   let rec loop i =
                     if i = n then ()
                     else begin
                         ar.(i).(i) <- C 0;
                         loop (i + 1)
                       end in
                   loop 0;
                   (n, ar)

  let set ((n, ar) : t) u v c = ar.(u).(v) <- C c

  let add x y =
    match x, y with
      C x, C y -> C (x + y)
    | _, _ -> Inf

  let compare x y =
    match x, y with
      C x, C y -> x - y
    | Inf, Inf -> 0
    | Inf, _ -> 1
    | _, Inf -> (-1)
                  
  let min x y =
    match compare x y with
      0 -> x
    | r when r > 0 -> y
    | _ -> x

  let max x y =
    match compare x y with
      0 -> x
    | r when r > 0 -> x
    | _ -> y
                
  let calc ((n, ar) : t) =
    let rec loop k i j =
      if k = n then ()
      else if i = n then loop (k + 1) 0 0
      else if j = n then loop k (i + 1) 0
      else let nc = add ar.(i).(k) ar.(k).(j) in
           ar.(i).(j) <- min nc ar.(i).(j);
           loop k i (j + 1) in
    loop 0 0 0

  let cost = function
      C x -> x
    | _ -> (-1)
end

let () =
  let solve n m =
    let ct = Wf.make m in
    let tt = Wf.make m in
    let rec read x =
      if x = 0 then ()
      else
        let a, b, c, t = scanf "%d %d %d %d " (fun w x y z -> (w-1, x-1, y, z)) in
        Wf.set ct a b c;
        Wf.set ct b a c;
        Wf.set tt a b t;
        Wf.set tt b a t;
        read (x-1)
    in
    read n;
    Wf.calc tt;
    Wf.calc ct;
    let k = scanf "%d " (fun x -> x) in
    let rec query x =
      if x = 0 then ()
      else
        let p, q, r = scanf "%d %d %d " (fun x y z -> (x-1, y-1, z)) in
        Wf.cost (if r = 0 then (snd ct).(p).(q) else (snd tt).(p).(q)) |> printf "%d\n";
        query (x - 1)
    in
    query k
  in
  let rec loop () =
    let n, m = scanf "%d %d " (fun x y -> (x, y)) in
    if n = 0 && m = 0 then ()
    else begin
        solve n m;
        loop ()
      end
  in loop ()

Measured memory_bytes: 6116
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using static System.Console;
using static System.Math;
using static MyIO;
using static MyUtil;

public class C { public static void Main() => (new Solver()).Solve(); }

public class Solver
{
	public void Solve()
	{
		long N = GetLong();
		var A = GetLongs(N);

		var L = new long[N + 1];
		L[0] = A[0];
		for(long i = 0; i < N; i++)
			L[i + 1] = gcd(L[i], A[i]);

		var R = new long[N + 1];
		R[N] = A[N - 1];
		for(long i = N - 1; i >= 0; i--)
			R[i] = gcd(R[i + 1], A[i]);

		long max = Max(L[N - 1], R[1]);
		for(long i = 0; i < N; i++)
			chmax(ref max, gcd(L[i], R[i + 1]));

		WriteLine(max);
	}
}

public static class MyIO
{
	private static string[] args = new string[0];
	private static int cnt = 0;
	private static IEnumerable<string> getArgs(long N) => Range(0, N).Select(_ => getArg());
	private static string getArg()
	{
		if(cnt == args.Length) { args = Console.ReadLine().Split(); cnt = 0; }
		return args[cnt++];
	}

	public static int GetInt() => int.Parse(getArg());
	public static long GetLong() => long.Parse(getArg());
	public static double GetDouble() => double.Parse(getArg());
	public static decimal GetDecimal() => decimal.Parse(getArg());
	public static string GetString() => getArg();
	public static char GetChar() => getArg()[0];
	public static int[] GetInts(long N) => getArgs(N).Select(int.Parse).ToArray();
	public static long[] GetLongs(long N) => getArgs(N).Select(long.Parse).ToArray();
	public static double[] GetDoubles(long N) => getArgs(N).Select(double.Parse).ToArray();
	public static decimal[] GetDecimals(long N) => getArgs(N).Select(decimal.Parse).ToArray();
	public static string[] GetStrings(long N) => getArgs(N).ToArray();
}

public static class MyUtil
{
	public static void chmax<T>(ref T x, T y) where T : IComparable<T> { if(x.CompareTo(y) < 0) x = y; }
	public static void chmin<T>(ref T x, T y) where T : IComparable<T> { if(x.CompareTo(y) > 0)	x = y; }
	public static void swap<T>(ref T x, ref T y) { T tmp = x; x = y; y = tmp; }
	public static long rightShift(long x, long y) => (x >> (int)y);
	public static long leftShift(long x, long y) => (x << (int)y);
	public static bool contains(long s, long x) => (rightShift(s, x) & 1L) == 1L;
	public static long gcd(long x, long y) => (y == 0) ? x : gcd(y, x % y);
	public static long lcm(long x, long y) => (x / gcd(x,y)) * y;	
	public static IEnumerable<int> Range(long start, long count) => Enumerable.Range((int)start, (int)count);
	public static void Sort(this List<string> source) => source.Sort(StringComparer.Ordinal);
}


Measured memory_bytes: 39800
#include<bits/stdc++.h>
using namespace std;
int i,j,n,m,a,c;
string b[100],r[100];
int main()
{
  for(cin>>n;i<n;i++)cin>>b[i];
  for(cin>>m;j<m;j++)cin>>r[j];
  for(i=0;i<n;i++,c=0){
    for(j=0;j<n;j++)if(b[i].compare(b[j])==0)c++;
    for(j=0;j<m;j++)if(b[i].compare(r[j])==0)c--;
    if(a<c)a=c;
  }
  cout<<(a<0?0:a)<<endl;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<cmath>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<numeric>
#include<functional>
#include<algorithm>
#include<bitset>
#include<tuple>
#include<unordered_set>
#include<unordered_map>
#include<random>
#include<array>
#include<cassert>
using namespace std;
#define INF (1<<29)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define uniq(v) v.erase(unique(all(v)),v.end())



int n, k;
int a[200000];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> k;
	rep(i, n)cin >> a[i];

	int cnt = 0, same = 0;
	rep(i, k - 1) cnt += a[i] < a[i + 1];
	same += cnt == k - 1;

	set<int> s;
	rep(i, k)s.insert(a[i]);

	int ans = !same;
	for (int i = k; i < n; i++) {
		s.erase(a[i - k]);
		cnt -= a[i - k] < a[i - k + 1];
		cnt += a[i - 1] < a[i];

		if (cnt == k - 1) {
			same++;
		}
		else if (a[i - k] < *s.begin() && *s.rbegin() < a[i]) {
		}
		else {
			ans++;
		}
		s.insert(a[i]);
	}
	cout << ans + min(same, 1) << endl;

	return 0;
}

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

int main() {
    ll n;
    cin >> n;
    ll ans = (n * (n - 1))/2;
    cout << ans << endl;
}


Measured memory_bytes: 256
#from collections import deque,defaultdict
from sys import stdin
input = stdin.readline
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

x,n = inm()
if n==0:
    print(x)
    exit()
p = inl()
mn = 999
for i in range(102):
    if i in p:
        continue
    d = abs(i-x)
    if d<mn:
        mn = d
        mni = i
print(mni)


Measured memory_bytes: 61832
n=int(input())
a=[int(i) for i in input().split()]
m=int(sum(a)/n)
m1=m-1
m2=m+1
s=0
s1=0
s2=0
for i in range(n):
    s+=(a[i]-m)**2
    s1+=(a[i]-m1)**2
    s2+=(a[i]-m2)**2
print(min(s,s1,s2))

Measured memory_bytes: 38256
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#include <iomanip>
#include <complex>
#include <bitset>
#include <stack>
 
using namespace std;
 
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f3f3f3f3fLL
#define SIZE 200105
#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
 
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
typedef pair<int,ll> pill; typedef pair<ll,int> plli; 
typedef pair<double, int> pdi;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
typedef complex<double> P;
//ll MOD = 1000000007;
ll MOD=998244353;
typedef ll Weight;
struct Edge {
	int src, dst;
	Weight weight;
};
bool operator < (const Edge &e, const Edge &f) {
	return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
	e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
int N;
ll dp[114514][3];
int main(){
	cin>>N;
	dp[0][0]=dp[0][1]=dp[0][2]=0;
	rep(i,N){
		ll A,B,C;
		cin>>A>>B>>C;
		dp[i+1][0]=max(dp[i][1],dp[i][2])+A;
		dp[i+1][1]=max(dp[i][0],dp[i][2])+B;
		dp[i+1][2]=max(dp[i][0],dp[i][1])+C;
	}

	cout<<max(max(dp[N][0],dp[N][1]),dp[N][2])<<endl;
}

Measured memory_bytes: 2560
#include <iostream>
#include <string>
#include <vector>
#include <stdlib.h>

using namespace std;

void display(vector<int> ary) {
  for (int i = 0; i < ary.size(); i++) {
    if (i > 0) cout << " ";
    cout << ary[i];
  }

  cout << endl;
}

void bubble_sort_and_display(vector<int> ary) {
  int count = 0, buf;
  bool flag = true;
  while (flag) {
    flag = false;
    for (int i = ary.size() - 1; i > 0; i--) {
      if (ary[i] < ary[i - 1]) {
        buf = ary[i];
        ary[i] = ary[i - 1];
        ary[i - 1] = buf;
        flag = true;
        count++;
      }
    }
  }
  display(ary);
  cout << count << endl;
}

int main(void) {
  int len;
  vector<int> ary;
  char s[200];

  cin >> len;

  for (int i = 0; i < len; i++) {
    cin >> s;
    ary.push_back(atoi(s));
  }

  bubble_sort_and_display(ary);

  return 0;
}

Measured memory_bytes: 3156
N = int(input())
A = [int(input()) for _ in range(N)]
AMax = max(A)
x = A.index(AMax)
Aelse = A[:x]+A[x+1:]
AelseMax = max(Aelse)
if AMax == AelseMax:
    for i in range(N):
        print(AMax)
else:
    for i in range(N):
        if x == i:
            print(AelseMax)
        else:
            print(AMax)

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int k;
    string s;
    cin >> k >> s;
    if (s.size() <= k) {
        cout << s;
    }
    else {
        cout << s.substr(0, k) << "...";
    }
    
    //cin >> x;
    //cout << "Output sentence"; 
    return 0;
}

Measured memory_bytes: 3632
//B - Judge Status Summary
//Hiia
#include <stdio.h>
#include <stdlib.h>//rannsuu, zettaichi(absolute)
#include <time.h>
//srand((unsigned int) time(0));
#include <math.h>//koudona keisann
#include <string.h>//hairetsu
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))
typedef long long ll;
//#define N 998244353
#define pi 3.1415926535897932384626433832

int gcd(int m,int n){if((0==m)||(0==n))return 0;while(m!=n)if(m>n)m=m-n;else n=n-m;return m;}
int lcm(int m,int n){if((0==m)||(0==n))return 0;return(m*n/gcd(m, n));}
int fact(int x){if(x==1) return(x);else return(x*fact(x-1));}//Kaijou x!
int ruijou(int base,int exponent){int i,answer=1;i=exponent;while(i!=0){answer=answer*base;--i;}return answer;}//ruijou base^exponent

long long int llgcd(long long int m,long long int n){if((0==m)||(0==n))return 0;while(m!=n)if(m>n)m=m-n;else n=n-m;return m;}
long long int lllcm(long long int m,long long int n){if((0==m)||(0==n))return 0;return(m*n/llgcd(m, n));}
long long int llfact(long long int x){if(x==1) return(x);else return(x*llfact(x-1));}//Kaijou
int llruijou(long long int base,long long int exponent){long long int i,answer=1;i=exponent;while(i!=0){answer=answer*base;--i;}return answer;}//ruijou base^exponent

int main()
{
  int n,c1=0,c2=0,c3=0,c4=0;
  char s[100];
  char s1[]="AC";
  char s2[]="WA";
  char s3[]="TLE";
  char s4[]="RE";

  scanf("%d", &n);
  for(int i = 1; i <= n; i++) {
    scanf("%s", s);

    if(strcmp(s, s1) == 0){
      c1++;
    }
    else if(strcmp(s, s2) == 0){
      c2++;
    }
    else if(strcmp(s, s3) == 0){
      c3++;
    }
    //if(strcmp(s, s4) == 0){
    else{
      c4++;
    }
  }

  printf("AC x %d\nWA x %d\nTLE x %d\nRE x %d\n", c1,c2,c3,c4);
  return 0;
}


Measured memory_bytes: 1708
#include<bits/stdc++.h>
using namespace std;
typedef  long long ll;
using vll=vector<ll>;
using vvll=vector<vll>;
using vi=vector<int>;
using vvi=vector<vector<int>>;
using vb=vector<bool>;
using pii=pair<int,int>;
using vpii=vector<pair<int,int>>;
using plli=pair<ll,int>;
using vplli=vector<pair<ll,int>>;
using pllll=pair<ll,ll>;
using vpllll=vector<pair<ll,ll>>;

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}

//pow(llpow,modpow)
template<class T> ll llpow(ll x,T n){ll ans=1;if(x==0)ans=0;while(n){if(n&1)ans*=x;x*=x;n>>=1;}return ans;}
long long modpow(long long a, long long n, long long mod) {long long res = 1;while (n > 0) {if (n & 1) res = res * a % mod;a = a * a % mod;n >>= 1;}return res;}
//最大公約数
template<class T> inline T gcd(T x,T y){if(y==0)return x; else {return gcd(y,x%y);}}
//最小公倍数
template<class T> inline T lcm(T x,T y){return x/gcd(x,y)*y;}
//逆元
long long modinv(long long a, long long m) {long long b = m, u = 1, v = 0;while (b) {long long t = a / b;a -= t * b; swap(a, b);u -= t * v; swap(u, v);}u %= m;if (u < 0) u += m;return u;}

#define rep(i, begin_i, end_i) for (ll i = (ll)begin_i; i < (ll)end_i; i++)
//試験導入
#define irep(i, end_i, begin_i) for (ll i = (ll)begin_i-1; i >= (ll)end_i; i--)

long long INF = 1LL<<60;
int cnt[110][2][4];
int main( ){
    string S;
    int K;
    cin>>S>>K;
    int N=S.size();
    cnt[0][0][0]=1;
    rep(i,0,N){
        int now=S[i]-'0';
        rep(j,0,2){
            rep(k,0,K+1){
                rep(d,0,10){
                    int ni=i+1,nj=j,nk=k;
                    if(d!=0)nk++;
                    if(nk>K)continue;
                    if(j==0){
                        if(d>now)continue;
                        else if(d<now)nj=1;
                    }
                    cnt[ni][nj][nk]+=cnt[i][j][k];
                }
            }
        }
    }
    cout<<cnt[N][0][K]+cnt[N][1][K]<<endl;
    return 0;
}




Measured memory_bytes: 256
#include <iostream>
#include <cmath>

using namespace std;
typedef long long ll;

int main(void){
  ll a,b,c;

  cin >> a >> b >> c;

  ll d = c - a - b;
  if(d > 0 && d * d > 4 * a * b){
  cout << "Yes" << endl;
  } else {
	  cout << "No" << endl;
  }

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
    int X,Y;
    cin >> X >> Y;
    vector<int> maney(205,0);
    maney.at(0) = 300000;
    maney.at(1) = 200000;
    maney.at(2) = 100000;
    if(X == 1 && Y == 1) {
        cout << maney.at(X - 1) + maney.at(Y - 1) + 400000;
    }else{
        cout << maney.at(X - 1) + maney.at(Y - 1);
    }
}


Measured memory_bytes: 256
n,a,b=map(int,input().split())
mm=max(a,b)
if a==0:
    print(0)
    exit()
if b==0:
    print(n)
    exit()
xx=n//(a+b)
ans=((xx-1)*a)
baaki=n-((xx-1)*a)-((xx-1)*b)
# print(baaki)
while baaki>0:
    temp=min(baaki,a)
    baaki-=temp
    ans+=temp
    if baaki<=0:
        break
    temp=min(baaki,b)
    baaki-=temp
    if baaki<=0:
        break 
print(ans)

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

const int N=1000100;
int n,q[N],ans;
char S[N],T[N];
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>(S+1)>>(T+1);
	int t=0,w=-1;
	for(int i=n,j=n;i;--i){
		if(T[i]==T[i-1]){
			if(S[i]!=T[i])ans=max(ans,1);
			continue;
		}
		for(j=min(j,i);j&&T[i]!=S[j];--j);
		if(!j){
			cout<<-1<<'\n';
			return 0;
		}
		for(;t<=w&&q[t]+t>i+w;++t);
		q[++w]=j;
		if(i!=j)ans=max(ans,w-t+2);
	}
	cout<<ans<<'\n';
	return 0;
}


Measured memory_bytes: 6144
n, q = gets.split.map(&:to_i)

tree = Array.new
1.upto(n-1) do |i|
  ai, bi = gets.split.map(&:to_i)
  tree[bi] = ai
end

points = Array.new(n + 1, 0)
1.upto(q) do |i|
  pi, xi = gets.split.map(&:to_i)
  points[pi] += xi
end

2.upto(n) do |node_n|
  points[node_n] += points[tree[node_n]]
end

points.shift
puts "#{points.join(" ")}\n"


Measured memory_bytes: 11388
#include<math.h>
#include<stdio.h>

int main(void)
{
	double x1,y1,x2,y2,d;

	scanf("%lf %lf %lf %lf", &x1,&y1,&x2,&y2);

	d = sqrt((x2 - x1)*(x2 - x1) + (y2 - y1)*(y2 - y1));

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

	return 0;
}


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

int main(){
    ll a,b,c;
    cin >> a >> b >> c;
    ll ca=0,cb=0,cc=0;
    if(a==b&&b==c&&a%2==0) cout << -1 << endl;
    else if(a%2||b%2||c%2) cout << 0 << endl;
    else {
        ll a1=b+c,b1=c+a,c1=a+b;
        while(a1%2==0){
            ca ++;
            a1 /= 2;
        }
        while(b1%2==0){
            cb ++;
            b1 /= 2;
        }
        while(c1%2==0){
            cc ++;
            c1 /= 2;
        }
        cout << min(ca,min(cb,cc)) << endl; 
    }
    return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize(2,3,"Ofast","unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define in inline
namespace fast_io
{
	char buf[1<<12],*p1=buf,*p2=buf,sr[1<<23],z[23],nc;int CC=-1,Z=0,Bi=0,ny;
	in char gc() {return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<12,stdin),p1==p2)?EOF:*p1++;}
	in ll read()
	{
		ll x=0;ny=1;while(nc=gc(),(nc<48||nc>57)&&nc!=EOF)if(nc==45)ny=-1;Bi=1;if(nc<0)return nc;
		x=nc-48;while(nc=gc(),47<nc&&nc<58&&nc!=EOF)x=(x<<3)+(x<<1)+(nc^48),Bi++;return x*ny;
	}
	in db gf() {int a=read(),y=ny,b=(nc!='.')?0:read();return (b?a+(db)b/pow(10,Bi)*y:a);}
	in int gs(char *s) {char c,*t=s;while(c=gc(),c<=32);*s++=c;while(c=gc(),c>32)*s++=c;return s-t;}
}
using namespace fast_io;
#define pb push_back
const int N=1e6+5,p=1e9+7;
int n,m,a[N],inv[N],fac[N],ans;
int A(int n,int m){return n<m?0:1ll*fac[n]*inv[n-m]%p;}
int C(int n,int m){return n<m?0:1ll*fac[n]*inv[m]%p*inv[n-m]%p;}
int main()
{
	n=read();m=read();inv[0]=inv[1]=fac[0]=fac[1]=1;
	for(int i=2;i<N;i++) inv[i]=1ll*(p-p/i)*inv[p%i]%p,fac[i]=1ll*fac[i-1]*i%p;
	for(int i=2;i<N;i++) inv[i]=1ll*inv[i]*inv[i-1]%p;
	for(int i=0;i<=n;i++)ans=(ans+1ll*(i&1?p-1:1)*A(m,i)%p*C(n,i)%p*A(m-i,n-i)%p*A(m-i,n-i)%p)%p;
	cout<<ans;
}
//Author: disangan233

Measured memory_bytes: 11428