akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

#define MOD 1000000007

typedef vector<int> vi;

int main()
{
	int n, m, i, j, e, tmp;
	scanf("%d %d", &n, &m);
	vi sc(n + 1), bk(n + 1);
	for (i = 0; i < m; i++) {
		scanf("%d", &e);
		bk[e] = 1;
	}
	if (bk[n] == 0)
		sc[n] = 1;
	for (i = n - 1; i >= 0; i--) {
		if (bk[i] == 0) {
			tmp = 0;
			if (i + 1 <= n)
				tmp = (tmp + sc[i + 1]) % MOD;
			if (i + 2 <= n)
				tmp = (tmp + sc[i + 2]) % MOD;
			sc[i] = tmp;
		}
	}
	printf("%d\n", sc[0]);
	return 0;
}

Measured memory_bytes: 1024
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace AtCoder
{
    class Program
    {
        private const int MODULO = 1000000007;
        private static string Read() { return Console.ReadLine(); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }

        static int Solve(int H, int W, string[] S)
        {
            var d = new int[H][];
            for (int i = 0; i < H; ++i) { d[i] = Enumerable.Repeat(int.MaxValue, W).ToArray(); }
            var q = new Queue<Tuple<int, int>>();
            d[0][0] = 0;
            q.Enqueue(new Tuple<int, int>(0, 0));
            while (q.Count > 0)
            {
                var p1 = q.Dequeue();
                int h1 = p1.Item1;
                int w1 = p1.Item2;
                foreach (var p2 in new[] { new Tuple<int, int>(h1 - 1, w1),
                                           new Tuple<int, int>(h1 + 1, w1),
                                           new Tuple<int, int>(h1, w1 - 1),
                                           new Tuple<int, int>(h1, w1 + 1) })
                {
                    int h2 = p2.Item1;
                    int w2 = p2.Item2;
                    if (0 <= h2 && h2 < H && 0 <= w2 && w2 < W)
                    {
                        if (S[h2][w2] == '.' && d[h2][w2] > d[h1][w1] + 1)
                        {
                            d[h2][w2] = d[h1][w1] + 1;
                            q.Enqueue(p2);
                        }
                    }
                }
            }
            int n = d[H - 1][W - 1];
            return (n < int.MaxValue) ? S.Sum(s => s.Count(c => c == '.')) - n - 1 : -1;
        }
        static void Main(string[] args)
        {
            int[] v = ReadInts();
            int H = v[0];
            int W = v[1];
            string[] S = new string[H];
            for (int i = 0; i < H; ++i) { S[i] = Read(); }
            Console.WriteLine(Solve(H, W, S));
        }
    }
}


Measured memory_bytes: 13652
import java.util.*;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    sc.nextLine();
    int[] p = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    int ans = 0;
    for (int i = 1; i < N-1; i++) {
      if ((p[i-1] < p[i] && p[i] < p[i+1]) || (p[i+1] < p[i] && p[i] < p[i-1])) ans++;
    }
    System.out.println(ans);
  }
}

Measured memory_bytes: 36292
#include<iostream>

using namespace std;
int main()
{
	int N,M,i,j,len[10010];
	cin >> N;
	for(i=N; i<1000; i++){
		for(j=1; j<10; j++){
			if(i == j*100 + j*10 + j){
				cout << i << endl;
				return 0;
			}
		}
		}
	
	
	return 0;
}


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

int main() {
  string op;
  int A ,B;
  cin >> A >> op >>B;
 
  if ( op == "+" ){
  cout << A + B <<endl;
  }
  else if ( op == "-" ){
  cout << A - B << endl;
  }
}  



Measured memory_bytes: 256
n, w = list(map(int, input().split()))
dp = [0] * (w + 1)
for _ in range(n):
    tmp_w, tmp_v = map(int, input().split())
    for j in range(w, tmp_w - 1, -1):
        dp[j] = max(dp[j], dp[j - tmp_w] + tmp_v)
print(dp[-1])

Measured memory_bytes: 41580
#include<bits/stdc++.h>
using namespace std;
char s[10];
int main(){
	int n,a=0,w=0,t=0,r=0;scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%s",s);
		switch(s[0]){
			case 'A':a++;break;
			case 'T':t++;break;
			case 'W':w++;break;
			default:r++;
		}
	}
	printf("AC x %d\nWA x %d\nTLE x %d\nRE x %d",a,w,t,r);
	return 0;
}

Measured memory_bytes: 3824
#include<iostream>
using namespace std;
int main()
{
	/*int t;
	cin>>t;
	double x1,y1,x2,y2,x3,y3;
	double a,k;
	while(t--)
	{
		cin>>x1>>y1>>x2>>y2>>x3>>y3;
		a=(y2-y1)/((x2-x1)*(x2-x1));
		k=(y3-y2)/(x3-x2);

	}*/
	int a,b,c,d;
	while(cin>>a>>b>>c>>d)
	{
		if(c>b||a>d)
			cout<<"0"<<endl;
		else if(c>=a&&d<=b)
			cout<<d-c<<endl;
		else if(a>=c&&b<=d)
			cout<<b-a<<endl;
		else if(b>=c&&a<=c&&d>=b)
			cout<<b-c<<endl;
		else if(d>=a&&c<=a&&b>=d)
			cout<<d-a<<endl;
	}
	return 0;
}

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

int main(){
    int n;
    cin>>n;
    int p;
    int ans=0;
    for(int i=1;i<=n;i++){
        cin>>p;
        if(p!=i) ans++;
    }
    if(ans>2) cout<<"NO"<<endl;
    else cout << "YES"<<endl;
    
    
}


Measured memory_bytes: 256
#include <cstdio>
#define REP(i,n) for(int i=0; i<n; i++)

long long n;
long long s[1048577];
long long right=0, left=0;
long long ans = 0;
long long sum=0, xr=0;

int main() {
  scanf("%lld",&n);
  REP(i,n) scanf("%lld", &s[i]);

  for(left=0; left<n; left++) {
    while (right < n && ((sum+s[right]) == (xr^s[right]))) {
      sum += s[right];
      xr ^= s[right];
      right++;
    }
    ans += right - left;
    if (left == right){
      right++;
    } else {
      sum -= s[left];
      xr ^= s[left];
    }
  }
  printf("%lld",ans);
}


Measured memory_bytes: 1664
#include <cstdio>
#define k 1024
#define r(i,a) for(int i=0;i<a;i++)
#define s(a) scanf("%d",&a);
#define m(a,b) a<b?a:b
int n,m,c[k],d[k],p[k];
int main(){
	s(n)s(m)
	r(i,n)s(d[i])
	r(i,m)s(c[i])
	r(i,n+1)p[i]=1<<29;
	p[0]=0;
	r(i,m)r(j,n)p[n-j]=m(p[n-j],p[n-j-1]+c[i]*d[n-j-1]);
	printf("%d\n",p[n]);
}

Measured memory_bytes: 1036
#include<bits/stdc++.h>
using namespace std;
int main(){
	long long a,b,c,ans=0;
	cin>>a>>b>>c;
	if(a%(b+c)>b)
		ans+=b;
	else
		ans+=a%(b+c);
	cout<<ans+(a/(b+c)*b);
	return 0;
}

Measured memory_bytes: 256
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>

#include <iostream>

using namespace std;

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define FORR(i, m, n) for(ll i = m;i >= n;i--)
#define REPO(i, n) for(int i = 1;i <= n;i++)
#define ll long long
#define INF 1999999999
#define MINF -1999999999
#define INF64 1999999999999999999
#define ALL(n) n.begin(),n.end()
#define MOD 1000000007

ll n, m, dp[2100][2100][2], ans = 0;
bool a[2100], b[2100];
string aa, bb;
int main() {
	cin >> n >> m;
	cin >> aa >> bb;
	REP(i, n)if (aa[i] == 'I')a[i] = true;
	REP(i, m)if (bb[i] == 'I')b[i] = true;
	REP(i, n + 1) {
		REP(j, m + 1) {
			REP(k, 2) {
				if (k != a[i])dp[i + 1][j][(k + 1) % 2] = max(dp[i + 1][j][(k + 1) % 2], dp[i][j][k] + (k + 1) % 2);
				if (k != b[j])dp[i][j + 1][(k + 1) % 2] = max(dp[i][j + 1][(k + 1) % 2], dp[i][j][k] + (k + 1) % 2);
			}
		}
	}
	REP(i, n + 1) {
		REP(j, m + 1) {
			ans = max(ans, dp[i][j][1]);
		}
	}
	if (ans == 0)cout << ans << endl;
	else cout << ans * 2 - 1 << endl;
}



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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, n) for (int i = 1; i <= (int)(n); i++)
using ll = long long;
using P = pair<ll,ll>;
#define pb push_back
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

/*
 string -> int : stoi(S);
 int -> string : to_string(N);
 Sのn文字以降をm文字取り出す : S.substr(n,m)
cout << fixed << setprecision(2) << 3.14 << endl; //3.1

 int: -2,147,483,648 ～ 2,147,483,647 (2×10^9)
 ll: -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 (9×10^18)

*/

int main() {

  ll n, m, count=0, ans=0;
  string s;
 
  cin >> n >> m;
  vector<int> h(n);
  rep(i,n) {
    cin >> h[i];
  }

  vector<vector<int>> path(n);
  rep(i,m){
    int a,b;
    cin >> a >> b;
    a--;
    b--;
    path[a].pb(b);
    path[b].pb(a); 
  }



  rep(i,n){
    bool no = true;
    int siz = path[i].size();
    rep(l,siz){
      if(h[i]<=h[path[i][l]]) no = false;
    }
    if(no) count++;
  }


  cout << count << endl;
}

Measured memory_bytes: 8712
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
//#pragma GCC target ("avx,tune=native")
//Use above if bruteforcing with lots of small operations. Or just use it anytime, there's no downside.
//AVX is better slightly
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef long double ld;

ll inv(ll a, ll b){
    return (a > 1 ? b - inv(b%a, a)*b/a : 1);
}

#define rc(s) return cout << s, 0
#define fi first
#define se second
#define L (nod << 1)
#define R (L | 1)
#define smax(X, Y) ((X) > (Y) ? (X) : (Y))
#define smin(X, Y) ((X) < (Y) ? (X) : (Y))

const ld e = 2.71828182845904523536028747;
const ld PI = 3.14159265359;
const ll inf = (1LL<<62);
const int iinf = (1<<30);
//CLOCKS_PER_SEC

string s;

int main(){
    //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    //ios_base::sync_with_stdio(0); cin.tie(0);
    //ifstream cin ("test.in");
    cin >> s;
    int n = s.length();
    s = "*" + s;
    for (int i=1; i<=n/2; i++){
        //cout << s[i] << s[n-i+1] << '\n';
        if (s[i] != s[n-i+1]) rc("No");
    }

    //cout << "pula1";
    int n1 = n / 2;
    for (int i=1; i<=n1/2; i++){
        //cout << s[i] << s[n1 - i + 1] << '\n';
        if (s[i] != s[n1 - i + 1]) rc("No");
    }

    //cout << "pula2";
    int st = n/2 + 2;
    for (int i=st, cnt = 1; cnt <= (n - st + 1) / 2; cnt++, i++)
        if (s[i] != s[n - (i - st + 1) + 1]) rc("No");
    rc("Yes");
    return 0;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
#ifndef FAST_IO
 #define IOS ios_base::sync_with_stdio(false);cin.tie(nullptr);
#endif
#define FILE_IO freopen("input.txt","r",stdin)
#define int long long
#define f first
#define s second
#define endl '\n'
#define all(c) c.begin(),c.end()
#define debug(x) cerr << #x << " = " << x << endl;
const int MO=1e9+7; 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T>void print(T t){for(auto &it:t)cout<<it<<" ";}
inline int powerexp(int a,int b,int m){int res=1;while(b){if(b&1)res=res*a%m;a=a*a%m,b>>=1;}return res%m;}
void solve(){
	int n;
	map<int,int> m;
	vector<int> ans;
	cin>>n;
	for(int i=0;i<n;i++){
       int x;
       cin>>x;
       m[x]++;
       if(m[x]==2 or m[x]==4)ans.emplace_back(x);
	}
	if((int)ans.size()<2){cout<<0;return;}
	sort(all(ans),greater<int>());
	cout<<ans[0]*ans[1]<<endl;
}
//-----------------------------
//comment from here for TOPCODER 
int32_t main(){
    IOS;
    solve();
    #ifdef LOCAL_DEFINE
    cerr<<"time elapsed "<<(double)clock()/CLOCKS_PER_SEC<<endl;
    #endif
}

Measured memory_bytes: 6528
using System;

class Program
{
    static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine());

        string[] input = Console.ReadLine().Split(' ');

        int ret = 0;

        bool hasError = false;
        while (!hasError)
        {
            for (int i = 0; i < input.Length; i++)
            {
                if (int.Parse(input[i]) % 2 == 0)
                {
                    input[i] = Convert.ToString(int.Parse(input[i]) / 2);
                }
                else
                {
                    hasError = true;
                }
            }
            if (!hasError)
            {
                ret++;
            }
        }

        Console.WriteLine(ret);
    }
}

Measured memory_bytes: 11220
public class Main{
  public void run(java.io.InputStream in, java.io.PrintStream out){
    java.util.Scanner sc = new java.util.Scanner(in);
/*answer*/
    int a, b, i, j, k, l;

    i = sc.nextInt();
    j = sc.nextInt();
    k = sc.nextInt();
    l = sc.nextInt();
    a = i + j + k + l;

    i = sc.nextInt();
    j = sc.nextInt();
    k = sc.nextInt();
    l = sc.nextInt();
    b = i + j + k + l;
    if(a < b)a = b;
    System.out.println(a);

    sc.close();
  }
  public static void main(String[] args){
    (new Main()).run(System.in, System.out);
  }
}

Measured memory_bytes: 17360
import java.util.*;

public class Main{
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		int num;
		int count = 0;
		num = scan.nextInt();
		for(int i = 0; i < num; i++){
			int tmp = scan.nextInt();
			if(tmp % 2 == 1){
				count++;
			}
		}
		if(count % 2 == 0){
			System.out.println("YES");
		} else {
			System.out.println("NO");
		}
	}
}

Measured memory_bytes: 32544
#include <iostream>
#include <queue>
#include <vector>
#include <utility>

int main(int argc, char const* argv[])
{
    int n, m;
    std::cin >> n >> m;

    int left_max = 1;
    int right_min = n;

    for(int i=0; i<m; ++i)
    {
        int l, r;
        std::cin >> l >> r;;

        left_max = std::max(left_max, l);
        right_min = std::min(right_min, r);
        //std::cout << left_max << " : " << right_min << std::endl;
    }

    if(left_max > right_min)
    {
        std::cout << 0 << std::endl;
    }
    else if(left_max == right_min)
    {
        std::cout << 1 << std::endl;
    }
    else
    {
        std::cout << (right_min - left_max) + 1 << std::endl;
    }
}

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

char C11,C12,C13,C21,C22,C23,C31,C32,C33;

int main(){
    cin >> C11 >> C12 >> C13;
    cin >> C21 >> C22 >> C23;
    cin >> C31 >> C32 >> C33;

    cout << C11 << C22 << C33;
    return 0;
}

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

int main() {
	long long n;
	std::cin >> n, ++n;
	std::vector<int> bit;
	std::list<int> ans;
	while (n) 
		bit.push_back(n & 1), n >>= 1;
	int cur = 0;
	for (int i = (int)(bit.size()) - 2; i >= 0; --i) {
		ans.push_back(++cur);
		if (bit[i]) ans.push_front(++cur);
	}
	for (int i = 1; i <= cur; ++i) ans.push_back(i);
	std::cout << ans.size() << std::endl;
	for (auto x : ans) std::cout << x << " ";
	std::cout << std::endl;
}


Measured memory_bytes: 256
from collections import defaultdict as dd
N, M = map(int, input().split())

Es = dd(dict)
for _ in range(M):
    a, b = map(int, input().split())
    Es[a][b] = Es[b][a] = 1

parents = [None] * (N+1)
parents[1] = 1
q = set([1])
while q:
    nq = set()
    for node in q:
        for to in Es[node]:
            if parents[to] is None:
                parents[to] = node
                nq.add(to)
    q = nq
print('Yes')
for i in range(2, N+1):
    print(parents[i])



Measured memory_bytes: 60780
import java.util.*;

class Main 
{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int x = sc.nextInt();
        
        if (x >= 30) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

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

int main(){
   int n,m;
   cin>>n>>m;
   int x;
   for(int i=0;i<m;i++){
       cin>>x;
       n-=x;
       if(n<0){
           cout<<-1;
           return 0;
       }

   }
   cout<<n;
   return 0;
}

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

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

Measured memory_bytes: 38384
w = int(input())
n = int(input())
lv = [i for i in range(1, w+1)]

for _ in range(n):
    a, b = list(map(int, input().split(",")))
    tmp = lv[a - 1]
    lv[a - 1] = lv[b - 1]
    lv[b - 1] = tmp

for v in lv:
    print(v)


Measured memory_bytes: 5600
n, y = map(int, input().split())
for i in range(n + 1):
    for j in range(n - i + 1):
        if i * 10000 + j * 5000 + (n - i - j) * 1000 == y:
            print(i, j, n - i - j)
            exit()
print("-1 -1 -1")

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

typedef pair<int, int> P;

struct edge
{
	edge(){}
	edge (int t, int c) { to = t; cost = c; }
	int to, cost;
};

int n, m;
int d[100];
bool f[100][100];
vector<int> a[100];
vector<edge> G[100];

const int inf = 1e9;

void dijkstra(int s)
{
	for (int i = 0; i < n; i++)
		a[i].clear();
	priority_queue<P, vector<P>, greater<P> > q;
	fill(d, d + n, inf);
	d[s] = 0;
	q.push(P(0, s));

	while (!q.empty()){
		P p = q.top(); q.pop();
		int v = p.second;
		if (d[v] < p.first) continue;
		
		for (int i = 0; i < G[v].size(); i++){
			edge e = G[v][i];
			if (d[e.to] == d[v] + e.cost){
				a[e.to].push_back(v);
			}
			if (d[e.to] > d[v] + e.cost){
				d[e.to] = d[v] + e.cost;
				q.push(P(d[e.to], e.to));
				a[e.to].clear();
				a[e.to].push_back(v);
			}
		}
	}
}

void dfs(int v)
{
	for (int i = 0; i < a[v].size(); i++){
		if (!f[v][a[v][i]]) continue;
		f[v][a[v][i]] = false;
		dfs(a[v][i]);
	}
}

int main()
{
	cin >> n >> m;
	for (int i = 0; i < m; i++){
		int a, b, c;
		cin >> a >> b >> c;
		a--; b--;
		f[a][b] = f[b][a] = true;
		G[a].push_back(edge(b, c));
		G[b].push_back(edge(a, c));
	}

	for (int i = 0; i < n; i++){
		dijkstra(i);
		for (int j = 0; j < n; j++){
			dfs(j);
		}
	}

	int cnt = 0;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			cnt += f[i][j];
		}
	}

	cout << cnt / 2 << endl;
}



Measured memory_bytes: 384
n, m = map(int, input().split())
a_list = list(map(int, input().split()))

border = sum(a_list) * (1/(4*m))

cnt = 0
for i in a_list:
    if cnt == m:
        print('Yes')
        exit()

    if i >= border:
        cnt += 1

if cnt >= m:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long lli;
typedef vector<lli> vll;
typedef vector<bool> vbl;
typedef vector<vector<lli> > mat;
typedef vector<vector<bool> > matb;
typedef vector<string> vst;
typedef pair<lli,lli> pll;
typedef pair<double,double> pdd;
typedef vector<map<lli,lli>> graph;

string s;

int main(){
	cin >> s;
	for(lli i = 0;i < s.size()-8;i++){
		cout << s[i];
	}
	cout << endl;
	return 0;
}

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

struct Edge
{
	int a, b;
	double cost;

	Edge () {}
	Edge (int a, int b, double cost) : a(a), b(b), cost(cost) {}

	bool operator < (const Edge &d) const
	{
		return ( cost < d.cost );
	}
};

struct Unionfind
{
	vector < int > par;

	Unionfind(int n)
	{
		par = vector < int >(n);
		for ( int i = 0; i < n; i++ ) {
			par[i] = i;
		}
	}

	void unite(int x, int y)
	{
		x = root(x), y = root(y);
		if ( x == y ) return;
		par[x] = y;
	}

	bool same(int x, int y)
	{
		return ( root(x) == root(y) );
	}

	int root(int n)
	{
		return par[n] = (par[n] == n ? n : root(par[n]));
	}
};

int main()
{
	int N, M;
	Edge edges[50005];
	vector < int > selected;

	cin >> N >> M;
	for ( int i = 0; i < M; i++ ) {
		cin >> edges[i].a >> edges[i].b >> edges[i].cost; --edges[i].a, --edges[i].b;
	}
	
	Unionfind tree(N);
	sort(edges, edges + M);
	int cost = 0;
	for ( int i = 0; i < M && selected.size() < N - 1; i++ ) {
		if ( !tree.same(edges[i].a, edges[i].b) ) {
			tree.unite(edges[i].a, edges[i].b);
			selected.push_back(i);
			cost += edges[i].cost;
		}
	}
		
	int ans = 0, num = 0;
	for ( int idx : selected ) {
		Unionfind tree2(N);
		int cnt = 0, cost2 = 0;
		for ( int i = 0; i < M; i++ ) {
			if ( i != idx && !tree2.same(edges[i].a, edges[i].b) ) {
				tree2.unite(edges[i].a, edges[i].b);
				cost2 += edges[i].cost;
				cnt++;
			}
		}
		if ( cnt < N - 1 || cost2 > cost ) {
			ans += edges[idx].cost;
			num++;
		}
	}

	cout << num << " " << ans << endl;

	return ( 0 );
}




Measured memory_bytes: 4076
#include<bits/stdc++.h>
using namespace std;
// make pair, tuple
// __gcd(int, int)
// bool isPrime(int n){
//       if(n <= 1)return false;
//       if(n <= 3)return true;
//       if(n % 2 == 0 || n % 3 == 0)return false;
//       for(int i = 5;i * i <= n;i += 6){
//             if(n % i == 0 || n % (i + 2) == 0)return false;
//       }
//       return true;
// }
// int countSubString(string s, string temp){
//       int ans = 0;
//       size_t f = s.find(temp);
//       while(f != string::npos){
//             ans++;
//             f = s.find(temp, f + 1);
//       }
//       return ans;
// }

int main(){
    int n;cin >> n;
    int arr[n + 5];
    int maxx = 0;
    int maxx2 = 0;
    for(int i = 0;i < n;i++){
        cin >> arr[i];
        if(arr[i] > maxx){
            maxx2 = maxx;
            maxx = arr[i];
        }
        else if(arr[i] > maxx2)maxx2 = arr[i];
    }
    for(int i = 0;i < n;i++){
        if(arr[i] == maxx)cout << maxx2<< "\n";
        else cout << maxx << "\n";
    }
}

Measured memory_bytes: 2432
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define rrep(i,a,b) for(ll i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()

ll dp[110][10][2];
int main(void){
    string n;
    ll k;

    cin >> n >> k;
    ll len = n.size();
    dp[0][1][0] = 1;
    dp[0][1][1] = ll(n[0]) - ll('0') - 1;
    dp[0][0][1] = 1;

    rep(i, 1, len){
        rep(j, 0, k + 1){
            //未満フラグ0 →0の場合
            if(n[i] == '0'){
                dp[i][j][0] += dp[i - 1][j][0];
            }else{
                if(j != 0){
                    dp[i][j][0] += dp[i - 1][j - 1][0];
                }
            }


            //未満フラグ1 →1の場合
            //0の場合
            dp[i][j][1] += dp[i - 1][j][1];

            //0でない値を入れる場合
            if(j != 0){
                dp[i][j][1] += dp[i - 1][j - 1][1] * 9;
            }

            //未満フラグ0 →1の場合
            if(j != 0){
                if(n[i] != '0'){
                    //0の場合
                    dp[i][j][1] += dp[i - 1][j][0];
                    //0でない値を入れる場合
                    dp[i][j][1] += dp[i - 1][j - 1][0] * (ll((n[i])) - ll('0') - 1);
                }
            }
        }
    }

    cout << dp[len - 1][k][1] + dp[len - 1][k][0] << endl;

}


Measured memory_bytes: 256
import java.util.*;class Main{public static void main(String[]z){Scanner s=new Scanner(System.in);String x;for(int T=s.nextInt(),t=0,i;t++<T;System.out.print(x)){char[][]d=new char[8][];for(x="Data "+t+":\n",i=0;i<8;++i)d[i]=s.next().toCharArray();Queue<int[]>l=new LinkedList<int[]>();int[]a={s.nextInt()-1,s.nextInt()-1},b;for(l.add(a);l.size()>0;)if(0<=(a=l.poll())[0]&&a[0]<8&&0<=a[1]&&a[1]<8&&d[a[1]][a[0]]>48)for(d[a[1]][a[0]]=48,i=-3;i<4;l.add(b),(b=a.clone())[1]+=i++,l.add(b))(b=a.clone())[0]+=i;for(char[]c:d)x+=new String(c)+"\n";}}}

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

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

  vector<int> t(N + 1, 0), x(N + 1, 0), y(N + 1, 0);
  for (int i = 1; i <= N; i++) {
    cin >> t[i] >> x[i] >> y[i];
  }

  for (int i = 1; i <= N; i++) {
    if (t[i] - t[i - 1] < abs(x[i] - x[i - 1]) + abs(y[i] - y[i - 1])) {
      cout << "No" << endl;
      return 0;
    }

    if ((t[i] - t[i - 1]) % 2 !=
        (abs(x[i] - x[i - 1]) + abs(y[i] - y[i - 1])) % 2) {
      cout << "No" << endl;
      return 0;
    }
  }

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

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

using namespace std;

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

	vector<int> d(N);
	for (int i = 0; i < N; i++)
	{
		cin >> d.at(i);
	}

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

	int mid_1st = d.at(0.5 * N - 1);
	int mid_2nd = d.at(0.5 * N);

	int res = 0;
	if (mid_1st != mid_2nd)
	{
		res = mid_2nd - mid_1st;
	}

	cout << res << endl;
}



Measured memory_bytes: 640
import sys
def input():
    return sys.stdin.readline()[:-1]

S = list(map(int, list(input())))
num = 0
dict = {}
dict[0] = 1
ans = 0

for i , n in enumerate(S[::-1]):
    num += n * pow(10,i,2019)
    cand = num % 2019
    if cand in dict.keys():
        dict[cand] += 1
    else:
        dict[cand] = 1

for key in dict.keys():
    ans += dict[key] * (dict[key] - 1) // 2
print(ans)


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

// macro
#define rep(i,n) for(i=0;i<n;i++)
#define ll long long
#define all(v) v.begin(), v.end()

// code starts
int main()
{
  int k;cin>>k;
  vector<int> x(k);
  vector<int> y(k);
  int i,j;
  rep(i,k)cin>>y[i]>>x[i];
  vector<int> a(8-k);
  rep(i,8-k)a[i]=i;
  vector<int> okx(0);
  vector<int> oky(0);
  rep(i,8)
  {
    rep(j,k)
    {
      if(x[j]==i)break;
      if(j==k-1)okx.emplace_back(i);
    }
  }
  rep(i,8)
  {
    rep(j,k)
    {
      if(y[j]==i)break;
      if(j==k-1)oky.emplace_back(i);
    }
  }
  vector<vector<bool>> put(8,vector<bool>(8,false));
  rep(i,k)put[y[i]][x[i]]=true;
  do
  {
    vector<vector<bool>> ch(8,vector<bool>(8));
    ch=put;
    rep(i,8-k)
    {
      ch[oky[i]][okx[a[i]]]=true;
    }
    int count=0;
    int out=false;
    for(i=0;i<8;i++)
    {
      count=0;
      for(j=0;i-j>=0;j++)
      {
        if(ch[i-j][j])count++;
      }
      if(count>=2)out=true;
    }
    for(i=8;i<=14;i++)
    {
      count=0;
      for(j=i-7;j<8;j++)
      {
        if(ch[i-j][j])count++;
      }
      if(count>=2)out=true;
    }
    for(i=0;i<8;i++)
    {
      count=0;
      for(j=0;j<8-i;j++)
      {
        if(ch[j+i][j])count++;
      }
      if(count>=2)out=true;
    }
    for(i=0;i<8;i++)
    {
      count=0;
      for(j=0;j<8-i;j++)
      {
        if(ch[j][j+i])count++;
      }
      if(count>=2)out=true;
    }
    if(out)continue;
    rep(i,8)
    {
      rep(j,8)
      {
        if(ch[i][j])cout<<'Q';
        else cout<<'.';
      }
      cout<<endl;
    }
  } while (next_permutation(all(a)));
  
}




Measured memory_bytes: 3156
#include <iostream>
#include <vector>

using namespace std;

int main() {
    int N;
    string S;
    cin >> N >> S;
    
    vector<int> e(N+1); e[0] = 0;
    for (int i=1; i<=N; i++) e[i] = e[i-1] + ((S[i-1] == 'E') ? 1 : 0);
    
    int min = N;
    for (int i=1; i<=N; i++) {
        int tmp = (i-1 - (e[i-1] - e[0])) + (e[N] - e[i]);
        min = (tmp < min) ? tmp : min;
    }
    
    cout << min << endl;
}

Measured memory_bytes: 1796
#include<iostream>
#include<climits>
#include<math.h>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<stdio.h>
#include <string>
#include <complex>
#include <functional>
using namespace std;
typedef pair<int,int> P;
double dat[100][100];
int dp[6][1010];//動的計画法
int prime[10000001];
char str[1010][1010];
vector<pair<int,int> > pc[100001];
int ABS(int a){return max(a,-a);}
int main(){
int m,n;
cin>>m>>n;
cout<<m-n+1<<endl;
    return 0;
}

Measured memory_bytes: 4352
n,m = raw_input().split()
ch = ['0','1','2','3','4','5','6','7','8','9']
f = True
s = raw_input()

for i in range(int(n)):
	if s[i] not in ch:
		f = False
if s[int(n)] != '-':
	f = False
for i in range(int(n)+1,len(s)):
	if s[i] not in ch:
		f = False
if len(s) > (int(n)+int(m)+1):
	f = False
if f:
	print "Yes"
else:
	print "No"

Measured memory_bytes: 2568
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <string>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define REP(i, n) for (int i = 0; i < (n); i++)
#define RREP(i, n) for (int i = (n) - 1; i >= 0; i--)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (a); i > (b); i--)
#define ALL(a) (a).begin(), (a).end()

int main() {
    int R;
    cin >> R;
    if (R < 1200) cout << "ABC" << endl;
    else if (R < 2800) cout << "ARC" << endl;
    else cout << "AGC" << endl;
    return 0;
}

Measured memory_bytes: 256
// Twitter@KonoLv1 2020年よりエンジニアデビュー予定

#include <stdio.h>
int main(void){
    
    int text_size;  //  文節の長さ
    int text5 = 0;  //   文節が5文字のカウント
    int text7 = 0;  //  文節が7文字のカウント
    int input_date = 3; //  入力される文節数
    
    for (int i = 0; i < input_date; i++){
        scanf("%d",&text_size);
        if (text_size == 5){
            text5++;
        }else if (text_size == 7){
            text7++;
        }
    }
    if (text5 == 2 && text7 == 1){
        printf("YES");
    }else{
        printf("NO");
    }
}


Measured memory_bytes: 128
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using static System.Console;
using static System.Math;
using static AtCoderTemplate.MyLibrary;

namespace AtCoderTemplate
{
    class Program
    {
        static void Main (string[] args)
        {
            string[] str = Console.ReadLine ().Split (' ');

            int X = int.Parse (str[0]);
            int N = int.Parse (str[1]);

            str = Console.ReadLine ().Split (' ');

            int[] p = new int[100];
            for (int i = 0; i < N; i++)
            {
                p[i] = int.Parse (str[i]);
            }

            int ans = 101;

            for (int i = 100; i >= 0; i--)
            {
                bool flag = true;
                for (int j = 0; j < N; j++)
                {
                    if (p[j] == i)
                    {
                        flag = false;
                        break;
                    }
                }

                if (flag == false) continue;

                if (Math.Abs (i - X) <= Math.Abs (ans - X))
                {
                    ans = i;
                }
            }

            Console.WriteLine (ans);

        }
    }

    class MyLibrary
    {

        // 自作の関数
        public static int MyFunction (int n)
        {
            return 0;
        }
    }
}

Measured memory_bytes: 27496
n=int(input())
a=list(map(int,input().split()))
lis=[0]*9
for num in a:
    lis[min(8,num//400)]+=1
kind=0
for i in range(8):
    if lis[i]>0:
        kind+=1
if kind==0:
    mini=1
else:
    mini=kind
maxi=kind+lis[8]
print(mini,maxi)
#print(lis)

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

using namespace std;

#ifdef SG
	#include <debug.h>
#else
	#define show(...)
	#define debug(...)
	#define deepen(...)
	#define timer(...)
#endif

#define ARG4(_1,_2,_3,_4,...) _4

#define forn3(i,l,r) for (int i = int(l); i < int(r); ++i)
#define forn2(i,n) forn3 (i, 0, n)
#define forn(...) ARG4(__VA_ARGS__, forn3, forn2) (__VA_ARGS__)

#define ford3(i,l,r) for (int i = int(r) - 1; i >= int(l); --i)
#define ford2(i,n) ford3 (i, 0, n)
#define ford(...) ARG4(__VA_ARGS__, ford3, ford2) (__VA_ARGS__)

#define ve vector
#define pa pair
#define tu tuple
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define fs first
#define sc second
#define all(a) (a).begin(), (a).end()
#define sz(a) ((int)(a).size())

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef unsigned char uc;
typedef pa<int, int> pii;
typedef pa<int, ll> pil;
typedef pa<ll, int> pli;
typedef pa<ll, ll> pll;
typedef ve<int> vi;

const ld pi = 3.1415926535897932384626433832795l;

template<typename T> inline auto sqr (T x) -> decltype(x * x) {return x * x;}
template<typename T1, typename T2> inline bool umx (T1& a, T2 b) {if (a < b) {a = b; return 1;} return 0;}
template<typename T1, typename T2> inline bool umn (T1& a, T2 b) {if (b < a) {a = b; return 1;} return 0;}
const int N = 1010;
int n;
int a[N];

int main () {
	cout.setf(ios::showpoint | ios::fixed);
	cout.precision(20);
#ifdef SG
	freopen((problemname + ".in").c_str(), "r", stdin);
//	freopen((problemname + ".out").c_str(), "w", stdout);
#endif
	cin >> n;
	n *= 2;
	
	forn(i, n)
		cin >> a[i];
	sort(a, a + n);
	int ans = 0;
	forn(i, n / 2) {
		ans += a[2 * i];
	}
	cout << ans << endl;
	return 0;
}


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

int main()
{
  int64_t N, a, b, t = 0;
  cin >> N;
  vector<pair<int64_t, int64_t>> A(N);
  for (int i = 0; i < N; i++)
  {
    cin >> a >> b;
    A.at(i) = make_pair(b, a);
  }
  sort(A.begin(), A.end());
  for (int i = 0; i < N; i++)
  {
    t += A.at(i).second;
    if (t > A.at(i).first)
    {
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
}

Measured memory_bytes: 3328
from collections import deque

N,M,*abf = map(int, open(0).read().split())
ab = [abf[i:i+2] for i in range(0, len(abf), 2)]

connected = [[]for _ in range(N+1)]
for u, v in ab:
    connected[u].append(v)
    connected[v].append(u)
    
d = deque([])
for x in connected[1]:
    if x == N:
        print('POSSIBLE')
        break
    else:
        d.append(x)
else:
    while d:
        temp = d.popleft()
        for x in connected[temp]:
            if x == N:
                print('POSSIBLE')
                break
        else:
            continue
        break
    else:
        print('IMPOSSIBLE')

Measured memory_bytes: 62548
import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val n = sc.nextInt()
    val m = sc.nextInt()
    val x = sc.nextInt()
    val a = (0 until m).map { sc.next().toInt() }
    println(problem094b(n, m, x, a))
}

fun problem094b(n: Int, m: Int, x: Int, a: List<Int>): Int {
    val a = a.toSet()
    var leftSum = 0
    var rightSum = 0
    for (i in 1 until n) {
        if (!a.contains(i)) continue
        if (i < x) {
            leftSum++
        } else {
            rightSum++
        }
    }
    return Math.min(leftSum, rightSum)
}

Measured memory_bytes: 31264
#include<stdio.h>
int main()
{
	long a[200000];
	long i, j, N;
	long sum1 = 0, min = 2000000000,sum2=0;
	scanf("%ld", &N);
	for (i = 0; i < N; i++)
	{
		scanf("%ld", &a[i]);
		sum1 += a[i];
	}
	for (i = 0; i < N-1; i++)
	{
		sum2 += a[i];
		if (sum1>2 * sum2)
		{
			j = sum1 - 2 * sum2;
			if (min < j)
				min = min;
			else
				min = j;
		}
		else
		{
			j =  2 * sum2 - sum1;
			if (min < j)
				min = min;
			else
				min = j;
		}
	}
	printf("%ld", min);
	return 0;
}

Measured memory_bytes: 1664
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  vector<int>a(n);
  int f=0;
  int co=1;
  for(int i=0;i<n;i++){
    cin >> a[i];
    if(i!=0){
      if(f==0){
	if(a[i-1]<a[i]){
	  f=1;
	}
	else if(a[i-1]>a[i]){
	  f=-1;
	}
      }
      if(f==1){
        if(a[i-1]>a[i]){
	  f=0;
	  co++;
	}
      }
      else if(f==-1){
	if(a[i-1]<a[i]){
	  f=0;
	  co++;
	}
      }
    }
  }
  cout << co << endl;
  return 0;
}


Measured memory_bytes: 764
//BISMILLAH
#include <bits/stdc++.h>
using namespace std;
int main(){
    
    int n,i,j;
    int cnt0 = 0;
    int cnt1 = 0;
    int cnt3 = 0;
    string s;
    cin >> n;
    cin >> s;
    
    for(i = 0;i<n;i++){
        if(s[i] == 'W') cnt0++;
        else if(s[i] == 'R') cnt1++; 
    }
    i = 0;
    j = n-1;
    while(i<j){
        if(s[i] == 'W' && s[j] == 'R'){
            swap(s[i],s[j]);
            i++;
            j--;
            cnt3++;
        }else if(s[i] == 'R' && s[j] == 'W'){
            i++;
            j--;
        }else if(s[i] == 'W' && s[j] == 'W') j--;
        else i++;
    }
      cout << min({cnt1,cnt0,cnt3}) << endl;
    return 0;
}



Measured memory_bytes: 3712
#![allow(unused, non_snake_case, dead_code, non_upper_case_globals)]
use {
    proconio::{marker::*, *},
    std::{cmp::*, collections::*, mem::*},
};
#[fastout]
fn main() {
    input! {//
        n:usize,m:usize,p:i64,
        mut abc:[(Usize1,Usize1,i64);m],
    }
    let mut edges = Vec::new();
    for (from, to, cost) in abc.iter() {
        edges.push((from, to, cost - p));
    }
    let mut dist = vec![-INF; n];
    dist[0] = 0;
    let mut ret = 0;
    for lp in 0..=n * 3 {
        for (from, to, cost) in edges.iter().cloned() {
            if dist[*from] != -INF && dist[*to] < dist[*from] + cost {
                dist[*to] = dist[*from] + cost;
                if lp > n {
                    dist[*to] = INF;
                }
            }
        }
        if lp == n - 1 {
            ret = dist[n - 1];
        }
    }
    if dist[n - 1] != ret {
        println!("{}", -1);
        return;
    }

    println!("{}", max(0, dist[n - 1]));
}
const INF: i64 = 1 << 60;


Measured memory_bytes: 2544
package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	N := ReadInt()
	as := ReadInts(N)
	Q := ReadInt()

	m := make(map[int]int)
	sum := 0
	for _, a := range as {
		m[a]++
		sum += a
	}

	for q := 0; q < Q; q++ {
		b, c := ReadInt(), ReadInt()
		// b を c にする
		counts := m[b]
		delete(m, b)
		m[c] += counts
		diff := (c - b) * counts
		sum += diff
		fmt.Println(sum)
	}
}

func ReadInts(n int) []int {
	v := make([]int, n)
	for i := 0; i < n; i++ {
		Scan(&v[i])
	}
	return v
}

var reader = bufio.NewReader(os.Stdin)

func Scan(a ...interface{}) {
	if _, err := fmt.Fscan(reader, a...); err != nil {
		panic(err)
	}
}
func ReadInt() (i int) { Scan(&i); return }


Measured memory_bytes: 10936
N,M = map(int,input().split())
LR = [[int(x) for x in input().split()] for _ in range(M)]

L_all,R_all = 1,N
for L,R in LR:
    L_all = max(L_all,L)
    R_all = min(R_all,R)

print(max(0,R_all+1-L_all))


Measured memory_bytes: 59992
#include<bits/stdc++.h>
using namespace std;
int main(){
	long long T1,T2,a,b,c,d,e,f;
	cin>>T1>>T2>>a>>c>>b>>d;
	if(a*T1+c*T2==b*T1+d*T2){
		cout<<"infinity";
		return 0;
	}
	if(a<b)swap(a,b),swap(c,d);
	e=a-b;f=c-d; 
	if(e*T1+f*T2>0&&e*T1>0){
		cout<<0;
		return 0;
	}
	if(e*T1+f*T2<0&&e*T1<0){
		cout<<0;
		return 0;
	}
	cout<<2ll*(((a-b)*T1)/(-e*T1-f*T2))+bool(((a-b)*T1)%(1ll*(-e*T1-f*T2)));
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define REP(i,x,y) for(ll i=x; i<=y; i++)
#define BIT(t) ((long long 1) << t)
using namespace std;
typedef long long ll;

int main(){
    ll n;
    cin >> n;
    cout << (n-2) * 180 << endl;
}

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

typedef long long LL;
typedef pair<int, int> II;

const int N = (int) 1e5 + 10;
int n, a[N];

int main() {
    #ifdef LOCAL
        freopen("Data.inp", "r", stdin);
        freopen("Data.out", "w", stdout);
    #endif

    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);

    int ans = 0;
    for (int i = 1; i <= n; ++i) ans += a[a[i]] == i;

    cout << ans / 2;
    return 0;
}


Measured memory_bytes: 768
//long time no ac
#include <bits/stdc++.h>
using namespace std;

#define 	ll				long long int
#define 	vll				vector<ll>
#define 	vi				vector<int>
#define		rep(i,n) 		for(i=0;i<n;i++)
#define		repe(i,I1,I2) 	for(i=I1;i<I2;i++)
#define		pb  			push_back
#define		mp  			make_pair
#define		endl			'\n'
#define 	mod				1000000007


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	ll n,t,i,ans;
	double k,c=1000000007,a;
	t=1;
	//cin>>t;
	
	while(t--)
	{
		cin>>n>>k>>a;
		double h[n];
		rep(i,n)
		{
			cin>>h[i];
			h[i]=k-(h[i]*0.006);
			if(c>abs(a-h[i]))
			{
				ans=i;
				c=abs(a-h[i]);
			}
		}
		
		cout<<ans+1;
		if(t!=0)
	   		cout<<"\n";
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int main()
{
    ll n,i,j,k,s=0,c=1,x=1,t;
    char ch;
    cin>>ch;
    if(ch>='A' && ch<='Z')
          cout<<'A';
    else cout<<'a';
}


Measured memory_bytes: 3628
#include <algorithm>
#include <climits>
#include <iostream>
#include <string>
#include <utility>
#include<vector>
#include<iomanip>
#include<map>
#include <queue>
#include<cmath>
#include<cstdio>
#include<iomanip>
#include<set>
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long int;
 
#define REP(i,n) for(ll i=0;i<(ll)(n);i++) //REP(i, 5) cout<<i;
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define MOD 1000000007 //10^9+7
//#define MOD 1
 
ll gcd(ll a, ll b) {
  ll tmp;
  if ( b > a) {
    tmp = a;
    a = b;
    b = tmp;
  }
  while (a % b !=0) {
    tmp = b;
    b = a % b;
    a = tmp;
  }
  return b;
}
 
const int MAX = 2000;

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;
}


void sosuu(ll n, vector<ll> &v){

  vector<ll> num(n, 0);

  FOR(i, 1, sqrt(n)){
    if(num[i]==0){
      FOR(j, 0, n/i){
        num[i+(j*i)] = 1;
      }
    }
  }
  REP(i, n){
    if(num[i]==0) v.push_back(i+1);
  }
}

ll GetDigit(ll num){
    ll digit=0;
    while(num!=0){
        num /= 10;
        digit++;
    }
    return digit;
}

ll power(ll a, ll b){
  ll ans = 1;
  if(b%2==0){
    REP(i, b/2){
      ans *= a;
      if(ans>1000000000){
        return -1;
      }
    }
    return ans * ans;
  }else{
    b = b/2;
    REP(i, b){
      ans *= a;
      if(ans>1000000000){
        return -1;
      }
    }
    return ans * ans* a;
  }
}

vector<pair<long long, long long> > prime_factorize(long long N) {
    vector<pair<long long, long long> > res;
    for (long long a = 2; a * a <= N; ++a) {
        if (N % a != 0) continue;
        long long ex = 0; // 指数

        // 割れる限り割り続ける
        while (N % a == 0) {
            ++ex;
            N /= a;
        }

        // その結果を push
        res.push_back({a, ex});
    }

    // 最後に残った数について
    if (N != 1) res.push_back({N, 1});
    return res;
}

int main(void){
  
  long long N;
  cin >> N;
  auto res = prime_factorize(N);

  ll sum = 0;

  for(ll i=0; i<res.size() ;i++){
    for(ll j=1;res[i].second-j>=0;j++){
      sum++;
      res[i].second -= j;
    }
  }
 
 // if(v.size()==0) cout<<"1"<<endl;
  cout<<sum<<endl;
  return 0;
  
}

Measured memory_bytes: 3724
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cstdio>

using namespace std;

typedef long long ll;

vector<ll> num;
ll ans[int(1e7)];
int l=1,r=0;

void cal(){
	for(int i=1;i<10;i++)
		ans[++r]=i;
	while(r>l) {
		ll cur=ans[l++];
		if(cur>1e11) return;
		num.push_back(cur);
		int back=cur%10;
		
		ans[++r]=cur*(ll)10+back;
		if(back!=0) ans[++r]=cur*(ll)10+back-1;
		if(back!=9) ans[++r]=cur*(ll)10+back+1;
	}
}

main() {
	
	cal();
	
	int k;
	
	cin>>k;
	
	sort(num.begin(),num.end()) ;
	
	cout<<num[k-1]<<endl;
}

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

#define endl '\n'
#define ff first
#define ss second
#define mp make_pair
#define pb push_back

typedef long long llong;
typedef pair<int, int> pii;

void solve() {

	int a, b, c;
	cin >> a >> b >> c;
	vector<int> arr = {a , b , c};
	sort(arr.begin(), arr.end());

	int h = arr[2];
	
	int w = arr[1];

	int l = arr[0];

	int hp1 = h / 2;
	int hp2 = h - hp1;

	llong red = (llong) w * hp1 * l;
	llong blue = (llong) w * hp2 * l; 

	cout << abs(red - blue);

}

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);

	#ifdef LOCAL
		ifstream in("in");
		cin.rdbuf(in.rdbuf());
	#endif

	solve();

	return 0;
}

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

int main(){


  while(1){
  int x, y;
  cin>>x>>y;
  if(x == 0 && y == 0) break;

  if(x > y) swap(x, y);
  cout<<x<<" "<<y<<endl;
 }

 return 0;
 }


Measured memory_bytes: 2988
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <map>
#include <iostream>
using namespace std;

int main() {
  int A,B,C;
  cin >> A >> B >> C;
  int mmm = max(A,max(B,C));
  int ans = mmm*3 - A - B - C;
  if (ans % 2 == 1) {
    ans += 3;
  }
  cout << ans/2 << endl;
}

Measured memory_bytes: 256
N = int(input())
abc = []
for i in range(N):
    abc.append(list(map(int, input().split())))

# dp[i][j] i日の時に行動jを起こす状況における最大幸福
dp = [[0]*3 for i in range(N)]
dp[0][0] = abc[0][0]
dp[0][1] = abc[0][1]
dp[0][2] = abc[0][2]

for i in range(N-1):
    for j in range(3):
        actions = list(set([0, 1, 2]) - set([j]))
        dp[i+1][j] = max(list(map(lambda x: abc[i+1][j]+dp[i][x], actions)))

print(max(dp[-1]))

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

#define all(x) begin(x), end(x)

using i64 = int_fast64_t;
using u64 = uint_fast64_t;
using f64 = double;
using p64 = pair<i64, i64>;

constexpr i64 INF = INT_FAST64_MAX / 2;

template<i64 M>
struct modint {
    i64 x;

    constexpr modint(const i64 y = 0) noexcept : x(y >= 0 ? y % M : (M - (-y) % M) % M) {}

    constexpr modint operator-() const noexcept { return modint(-x); }
    constexpr modint operator+(const modint &rhs) const noexcept { return modint(*this) += rhs; }
    constexpr modint operator-(const modint &rhs) const noexcept { return modint(*this) -= rhs; }
    constexpr modint operator*(const modint &rhs) const noexcept { return modint(*this) *= rhs; }
    constexpr modint operator/(const modint &rhs) const noexcept { return modint(*this) /= rhs; }

    constexpr modint &operator+=(const modint &rhs) noexcept {
        x += rhs.x;
        if (x >= M) x -= M;
        return *this;
    }

    constexpr modint &operator-=(const modint &rhs) noexcept {
        if (x < rhs.x) x += M;
        x -= rhs.x;
        return *this;
    }

    constexpr modint &operator*=(const modint &rhs) noexcept {
        x = x * rhs.x % M;
        return *this;
    }

    constexpr modint &operator/=(const modint &rhs) noexcept {
        i64 a = rhs.x, b = M, u = 1, v = 0;
        while (b > 0) {
            i64 t = a / b;
            swap(a -= t * b, b);
            swap(u -= t * v, v);
        }
        *this *= u;
        return *this;
    }

    friend ostream &operator<<(ostream &os, const modint &p) {
        return os << p.x;
    }

    friend istream &operator>>(istream &is, modint &a) {
        i64 t;
        is >> t;
        a = modint(t);
        return is;
    }
};

constexpr i64 MOD = 1 ? 1'000'000'007 : 998'244'353;
using m64 = modint<MOD>;
constexpr m64 operator"" _m(unsigned long long n) { return m64(n); }

vector<vector<optional<m64>>> dp;
vector<vector<i64>> g;

m64 dfs(i64 color, i64 idx, i64 from) {
    if (dp[color][idx]) return *dp[color][idx];

    m64 res = 1;
    for (auto& nxt : g[idx]) {
        if (nxt == from) continue;
        res *= dfs(0, nxt, idx) + dfs(1, nxt, idx) * !color;
    }
    return dp[color][idx].emplace(res);
}

void solve() {
    i64 n;
    cin >> n;

    g.resize(n);
    for (i64 i = 0; i < n - 1; i++) {
        i64 x, y;
        cin >> x >> y, x--, y--;
        g[x].emplace_back(y);
        g[y].emplace_back(x);
    }

    dp.resize(2, vector<optional<m64>>(n));
    cout << dfs(0, 0, -1) + dfs(1, 0, -1) << endl;
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
}


Measured memory_bytes: 20076
while True:
    H, W = map(int, input().split())
    if H == W == 0:
        break
    for i in range(H):
        for j in range(W):
            if (i + j) % 2 == 0:
                print('#', end = '')
            else:
                print('.', end = '')
        print()    
    print()


Measured memory_bytes: 7000
using System;

class ITP1_1_C
{
    public static void Main()
    {
        const int iNum = 2; //??\???????????????????????°

        /* Input */
        string strInput = Console.ReadLine();

        /* ?????????????????? */
        string[] strInputValue = new string[iNum];
        strInputValue = strInput.Split(' ');

        /* ??????????´? */
        int iHeight = int.Parse(strInputValue[0]);
        int iWidth = int.Parse(strInputValue[1]);

        /* ?????? */
        int iLength = iHeight * 2 + iWidth * 2; //??¨?????????
        int iSurface = iHeight * iWidth;    //??¢???

        /* Output */
        Console.WriteLine("{0} {1}", iSurface, iLength);
    }
}

Measured memory_bytes: 9192