akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
typedef pair<int,int> Pii;
int dp[505][20004]; // dp[i] := i????£????????????±?????????
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int M, N; cin >> M >> N;
  int P[M]; FOR(i,0,M) cin >> P[i];
  sort(P, P + M);
  reverse(P, P + M);
  int sum[M+1];
  sum[0] = 0;
  FOR(i,0,M) sum[i+1] = sum[i] + P[i];
  vector<Pii> v(N);
  FOR(i,0,N) {
    int c, e;
    cin >> c >> e;
    v[i] = Pii(c, e);
  }
  //sort(v.begin(), v.end());
  FOR(i,0,505) FOR(j,0,20004) dp[i][j] = 1e9;
  dp[0][0] = 0;
  FOR(i,0,N) {
    FOR(j,0,20004) {
      if(dp[i][j] == 1e9) continue;
      // ????????????
      dp[i+1][j] = min(dp[i+1][j], dp[i][j]);
      // ??±i?????????
      if(j + v[i].first < 20004) dp[i+1][j+v[i].first] = min(dp[i+1][j+v[i].first], dp[i][j] + v[i].second);
    }
  }
  int ans = 0;
  FOR(i,0,20004) {
    int s = i <= M ? sum[i] : sum[M];
    ans = max(ans, s - dp[N][i]);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 42752
H, W = map(int, input().split())
grid = [[i for i in input()] for i in range(H)]

jud = 'Yes'
for i in range(H):
    for j in range(W):
        if grid[i][j] == '#':
            try:
                if grid[i-1][j] == grid[i][j-1] == grid[i][j+1] == grid[i+1][j] == '.':
                    jud = 'No'
                else:
                    continue
            except Exception:
                break

print(jud)


Measured memory_bytes: 3064
n, l = map(int, input().split())

a = [[] * l for i in range(n)]
for i in range(n):
    I = input()
    for j in range(l):
        a[i].append(I[j])
# print(a)
b = a
for i in range(l-1,-1,-1):
    b = sorted(b, key=lambda x: x[i])

ans = []
for i in range(n):
    ans.append("".join(b[i]))
print("".join(ans))


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

using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n)  FOR(i,0,n)

int n,a,b;

int sum_digit(int p){
  if (p==0) return 0;
  return p%10+sum_digit(p/10);
}

int main(){
  scanf("%d %d %d",&n,&a,&b);
  int i = 1;
  int tmp;
  int ans=0;
  while(i<n+1){
    tmp = sum_digit(i);
    if (tmp<a) {
      i += a-tmp;
      continue;
    }
    if (b<tmp){
      i += (10-i%10);
      continue;
    }
    ans +=i;
    i++;
  }


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


Measured memory_bytes: 256
"""
rootを決めて、aから必ずrootを通ってbに到達するとする
aとbのlcaより上は、+2されることになるので、実質通っていないのと同値
どんな木であっても、自分自身が偶数回(0を含む)でてこないと
ノードの値は偶数にはなりえない
"""
n, m = map(int, input().split())
cnts = [0] * (n+1) 
for i in range(m):
    a,b = map(int, input().split())
    cnts[a] += 1
    cnts[b] += 1
if all([c%2 == 0 for c in cnts]):
    print("YES")
else:
    print("NO")

Measured memory_bytes: 10740
#include<stdio.h>

int main(void)

{

 int n,x,min,max;

 long sum;


 int i;


 scanf("%d %d",&n,&x);

 min=max=sum=x;


 for(i=1; i<n; i++){

  scanf("%d",&x);

  sum +=x;


  if(max<x)


   max=x;


  if(min>x)


   min=x;


  }


  printf("%d %d %ld\n",min,max,sum);


 return 0;


}


 


 

Measured memory_bytes: 600
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <cassert>
#include <utility>
#include <iomanip>

using namespace std;

#define sz(x) (int) x.size()
#define unique(x) x.erase(unique(x.begin(), x.end()), x.end())
#define all(a) a.begin(), a.end()
#define sqr(x) ((x) * (x)) 
#define y1 aksjdaskdjksjfksdjf
#define left kdnvldvoiwejifejg
#define right lkdsjflksdjfdjfk
#define prev asdasfsadjkjsdfjs

long long n;

int main() { 

  cin >> n;

  if (n & 1) {
    cout << 0 << endl;
    return 0;
  }

  long long res = 0;

  for (long long fv = 10; fv <= n; fv *= 5) {
    res += n / fv;
  }

  cout << res << endl;

  return 0;
}


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

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

const long long MOD = 1000000007;

int main(){
  string s;
  cin >> s;
  rep(i,s.size()) cout << "x";
  cout << endl;
  
}


Measured memory_bytes: 256
N = int(raw_input())
A = list(map(int,raw_input().split()))
A.sort()
MOD = 10**9 + 7
def calc(a):
	if N % 2 == 0:
		B = [int(i/2)*2 + 1 for i in range(0,N)]
		if A != B:
			return 0
	else:
		B = [int(i/2)*2 for i in range(1,N+1)]
		if A != B:
			return 0
	return 2 ** int(N/2)

print(calc(A) % MOD)

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


int main(){
  string s;
  cin >> s;
  sort(s.begin(),s.end());
  
  string t;
  cin >> t;
  sort(t.begin(),t.end());
  reverse(t.begin(),t.end());
  if (s < t)cout<<"Yes"<<endl;
  else cout << "No" << endl;
}


Measured memory_bytes: 256
from heapq import heappop, heappush


n,m = map(int,input().split())
A = list(map(int,input().split()))
pq = []
ans = 0

for a in A:
    heappush(pq, [-a, 1])
    
for _ in range(m):
    b,c = map(int,input().split())
    heappush(pq, [-c, b])

for i in range(n):
    c,b = heappop(pq)
    c = -c
    ans += c
    if b > 1:
        b -= 1
        heappush(pq, [-c, b])
        
print(ans)

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

int main() {
	int h, w; cin >> h >> w;
	vector<vector<int>> v = {{ -1, 1}, { -1, 0}, { -1, -1}, {0, 1}, {0, -1}, {1, 1}, {1, 0}, {1, -1}};
	vector<vector<char>>grid(h + 2, vector<char>(w + 2, '.'));
	for (int i = 1; i <= h; i++) {
		for (int j = 1; j <= w; j++) {
			cin >> grid[i][j];
		}
	}
	for (int i = 1; i <= h; i++) {
		for (int j = 1; j <= w; j++) {
			if (grid[i][j] != '#') {
				int cnt = 0;
				for (int k = 0; k < 8; k++) {
					if (grid[i + v[k][0]][j + v[k][1]] == '#')cnt++;
				}
				cout << cnt;
			} else {
				cout << '#';
			}
		}
		cout << endl;
	}
}

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

int main() {
  int n, m;
  cin >> n >> m;
  vector<int> a(m);
  rep(i, m) cin >> a[i];

  int total = 0;
  rep(i, m) total += a[i];

  int ans = 0;
  if (total > n) {
    ans = -1;
  } else {
    ans = n - total;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3668
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i,n,k) for(ll i=(n);i<(k);i++)
#define ALL(a)  (a).begin(),(a).end()
ll ans=0;
void Main(){
    ll a;cin>>a;
    ll b;cin>>b;
    if(a>b){
        For(i,0,a) cout<<b;
        cout<<endl;
    }
    else{
        For(i,0,b) cout<<a;
        cout<<endl;
    }
}
int main(){
    Main();
    return 0;
}

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

int main()
{
	int n, u, k, v[101], VM[101][101];
	memset(VM, 0, sizeof(VM));
	cin >> n;

	for (int i = 1; i <= n; i++)
	{
		cin >> u >> k;

		for (int j = 1; j <= k; j++)
		{
			cin >> v[j];
			VM[u][v[j]] = 1;
		}
	}

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j < n; j++)
			cout << VM[i][j] << " ";

		cout << VM[i][n] << endl;
	}

	return 0;
}


Measured memory_bytes: 3144
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

long se(map<int, vector<long>> &t, int bas, int key, int r){
    if(key==3){
        int p=t[bas+key].size()-1;
        return t[bas+key][min(p, r/(bas+key))];
    }
    long now=0;
    for(int i=0; r/(bas+key)>=i && i<t[bas+key].size(); ++i) now=max(now, t[bas+key][i]+se(t, bas, key+1, r-i*(bas+key)));
    return now;
}

int main() {
	int N, W; cin >> N >> W;
	map<int, vector<long>> mp;
	int small;
	for(int i=0; i<N; ++i){
	    int w;
	    long v;
	    cin >> w >> v;
	    if(i<1){
	        small=w;
	        for(int j=0; j<4; ++j) mp[w+j].push_back(0);
	    }
	    mp[w].push_back(v);
	}
	for(int i=0; i<4; ++i){
	    sort(mp[small+i].begin()+1, mp[small+i].end(), greater<long>());
	    for(int j=1; j<mp[small+i].size(); ++j) mp[small+i][j] += mp[small+i][j-1];
	}
	long ans=se(mp, small, 0, W);
	cout << ans << endl;
	return 0;
}


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

#define int long long
#define endl "\n"
#define REP(i,a,n) for(int i=a;i<n;++i)
#define REPR(i,a,n) for(int i=a;i>n;--i)
#define RUP(a,b) ((a+b-1)/(b))
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define mt make_tuple
//#define MOD 1000000007
#define INF LLONG_MAX/2

typedef long long ll;
typedef pair<int,int> Pii;
typedef tuple<int,int,int> Tiii;
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef vector<Pii> VPii;
typedef vector<string> Vs;

template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T> void YesNo(T a) {cout<<(a?"Yes":"No")<<endl;}
template<class T> void YESNO(T a) {cout<<(a?"YES":"NO")<<endl;}
void vin(Vi &v){REP(i,0,(v).size()) cin>>v[i];}
void vin(Vi &v,Vi &v2){REP(i,0,(v).size()) cin>>v[i]>>v2[i];}
void vout(Vi &v){for(int i=0;i<(v).size();i++) cout<<v[i]<<" ";cout<<endl;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
void uniq(Vi &v){sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());}
int ctoi(char c){if(c>='0'&&c<='9'){return c-'0';}return 0;}
void accum(Vi &v){REP(i,1,(v).size()) v[i]+=v[i-1];}
bool comp(Pii a,Pii b){
    if(a.second != b.second) return a.second<b.second;
    else return a.first<b.first;
}


void solve(long long h, long long n, std::vector<long long> a, std::vector<long long> b){
    const int nmax=1000,hmax=10000;
    VVi dp(nmax+10,Vi(hmax+10,INF/2));
    REP(i,0,n+1){
        dp[i][0]=0;
    }
    REP(i,0,h+1){
        dp[0][i]=0;
    }
    // REP(i,0,n+1){
    //     REP(j,0,h){
    //         cout<<dp[i][j]<<" ";
    //     }
    //     cout<<endl;
    // }
    REP(i,1,n+1){
        REP(j,1,h+1){
            if(j<=a[i-1]) chmin(dp[i][j],b[i-1]);
            if(j-a[i-1]>0){
                if(i>1) chmin(dp[i][j],dp[i-1][j-a[i-1]]+b[i-1]);
                chmin(dp[i][j],dp[i][j-a[i-1]]+b[i-1]);
            }
            if(i>1){
                chmin(dp[i][j],dp[i-1][j]);
            }
        }
    }

    // REP(i,0,n+1){
    //     REP(j,0,h+1){
    //         cout<<dp[i][j]<<" ";
    //     }
    //     cout<<endl;
    // }

    cout<<dp[n][h]<<endl;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
signed main(){
    long long H;
    scanf("%lld",&H);
    long long N;
    scanf("%lld",&N);
    std::vector<long long> A(N);
    std::vector<long long> B(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&A[i]);
        scanf("%lld",&B[i]);
    }
    solve(H, N, std::move(A), std::move(B));
    return 0;
}


Measured memory_bytes: 79360
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using static System.Convert;
using static System.Console;
using static System.Math;
class MainClass
{
	static void Main(string[] args)
	{
		Answer();
	}
	public static void Answer()
	{
			var N = Console.ReadLine();
			var a = Console.ReadLine().Split(' ');
			int max = 0;int min = 1000000001;
			for(int i = 0; i < a.Length; i++)
			{
				var tmp = int.Parse(a[i]);
				if (max < tmp)
					max = tmp;
				if (tmp < min)
					min = tmp;
			}
			WriteLine(max - min);
	}
  
    public class ConsoleInput
    {
        private readonly System.IO.TextReader _stream;
        private char _separator = ' ';
        private Queue<string> inputStream;
        public ConsoleInput(System.IO.TextReader stream, char separator = ' ')
        {
            this._separator = separator;
            this._stream = stream;
            inputStream = new Queue<string>();
        }
        public string Read
        {
            get
            {
                if (inputStream.Count != 0) return inputStream.Dequeue();
                string[] tmp = _stream.ReadLine().Split(_separator);
                for (int i = 0; i < tmp.Length; ++i)
                    inputStream.Enqueue(tmp[i]);
                return inputStream.Dequeue();
            }
        }
        public string ReadLine { get { return _stream.ReadLine(); }}
        public int ReadInt { get { return int.Parse(Read); }}
        public long ReadLong { get { return long.Parse(Read); }}
        public double ReadDouble { get { return double.Parse(Read); }}
        public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret;}
        public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret;}
        public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret;}
    }
}

Measured memory_bytes: 13140
N = int(input())
h = list(map(int, input().split()))
INF = 10**15
dp = [INF]*N
dp[0] = 0

for i in range(1,N):
	dp[i] = min(dp[i], dp[i-1]+abs(h[i]-h[i-1]))
	if i > 1:
		dp[i] = min(dp[i], dp[i-2]+abs(h[i]-h[i-2]))
print(dp[N-1])


Measured memory_bytes: 13928
#include <bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(long long i=a; i<b; i+=1)
#define repr(i,a,b) for(long long i=a; i<=b; i+=1)
#define vec vector<ll>
#define map map<string,int>
#define repa(p,A) for(auto p:A)
#define pb push_back
#define sort(a) sort(a.begin(),a.end())
#define reverse(a) reverse(a.begin(),a.end())

using namespace std;
 ll CNB(ll i) {
   return i*(i-1)/2;
 }

int main(){
  ll N;
  cin>>N;
  vector<string> A(N);
  rep(i,0,N) {
    cin>>A[i];
    sort(A[i]);
  }
  map B;
  rep(i,0,N) {
    B[A[i]]++;
  }
  ll count=0;
  
  for(auto p:B) {
    //cout<<CNB(p.second)<<endl;
    count+=CNB(p.second);
    
    
  }
  

  cout<<count<<endl;
    
  
      
    
}

Measured memory_bytes: 18176
#include <set>
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <limits>
#include <map>
#include <numeric>

#define ll long long
using namespace std;
static ll imin = std::numeric_limits<ll>::min();
static ll imax = std::numeric_limits<ll>::max();
#define rep(i, n) for(int i = 0; i<n; ++i)
#define rep1(i, n) for(int i = 1; i<n; ++i)
#define rev_rep(i, n) for(int i = n - 1; i >= 0; --i)
#define dump(x) cout << #x << ":" << x << "\n";
#define all(v) v.begin(), v.end()

template<class T1, class T2>
std::ostream& operator << (std::ostream& os, std::map<T1, T2>& mp);
template<class T1, class T2>
std::ostream& operator << (std::ostream& os, std::pair<T1, T2>& pair);
template<class T>
std::ostream& operator << (std::ostream& os, std::vector<T>& vec);
template<class T1, class T2>
std::ostream& operator << (std::ostream& os, std::pair<T1, T2>& pair){
  os << '(' << pair.first << ',' << pair.second << ')';
  return os;
}

template<class T>
std::ostream& operator << (std::ostream& os, std::vector<T>& vec){
  std::size_t n = vec.size();
  if(n == 0){
    return os;
  }
  os << " ";
  for(int i = 0; i<n - 1; ++i){
    os << vec[i] << " ";
  }
  os << vec[n - 1];
  os << std::endl;
  return os;
}

template<class T1, class T2>
std::ostream& operator << (std::ostream& os, std::map<T1, T2>& mp){
  std::size_t n = mp.size();
  if(n == 0){
    return os;
  }
  os << " ";
  for(auto && x:mp){
    os << x << " ";
  }
  os << std::endl;
  return os;
}

#ifndef BOOST_TEST_MAIN
int main(int const argc, char const** argv){
  ll N;
  cin >> N;
  vector<ll> t(N + 1), x(N + 1), y(N + 1);
  t[0] = 0;
  x[0] = 0;
  y[0] = 0;

  rep1(i, N + 1){
    cin >> t[i] >> x[i] >> y[i];
  }

  // dump(t);
  // dump(x);
  // dump(y);
  rep(i, N){
    if(!(t[i + 1] - t[i] >= abs(x[i + 1] - x[i]) + abs(y[i + 1] - y[i]) && (t[i + 1] - t[i]) % 2 == (abs(x[i + 1] - x[i]) + abs(y[i + 1] - y[i])) % 2)){
      // dump(t[i + 1]);
      // dump(x[i + 1]);
      // dump(y[i + 1]);
      // cout << i;
      cout << "No";
      return 0;
    }
  }
  cout << "Yes";
}
#endif


Measured memory_bytes: 2560
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<utility>
#define REP(i,n) for(int i = 0;i < (n);i++)
#define pb push_back
using namespace std;
const int INF = 1e9;
typedef long long ll;

int main(){
  ll x,y,z;
  cin >> x >> y>> z;
  ll sum = 0;
  x -= z;
  while(1){
    if(x-y-z < 0)
      break;
    x -= y;
    sum++;
    x -= z;
  }
  cout << sum << endl;
  return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <string>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
using namespace std;

int main()
{
	unsigned long long a, b, x;
	cin >> a >> b >> x;

	unsigned long long ans, mod, st, ed, mod2;
	mod = a % x;
	if (mod == 0) {
		st = a;
	}
	else {
		st = a + (x - mod);
	}

	mod2 = b % x;
	ed = b - mod2;

	// cout << st << " " << ed << endl;
	if (st > ed) {
		ans = 0;
	}
	else {
		ans = (ed - st) / x;
		ans += 1;
	}

	cout << ans << endl;
}

Measured memory_bytes: 256
import java.awt.Point;
import java.util.*;

public class Main {
	int N;
	List<Point> redPoints;
	List<Point> bluePoints;
	boolean[] redUsed;
	Comparator<Point> compX = new Comparator<Point>() {
		@Override
		public int compare(Point o1, Point o2) {
			if (o1.x < o2.x) {
				return -1;
			} else if (o1.x > o2.x) {
				return 1;
			} else {
				return 0;
			}
		}
	};

	Comparator<Point> compY = new Comparator<Point>() {
		@Override
		public int compare(Point o1, Point o2) {
			if (o1.y > o2.y) {
				return -1;
			} else if (o1.y < o2.y) {
				return 1;
			} else {
				return 0;
			}
		}
	};

	Main() {
		Scanner in = new Scanner(System.in);
		N = in.nextInt();
		this.redPoints = new ArrayList<>(N);
		for (int i = 0; i < N; ++i) {
			int a = in.nextInt();
			int b = in.nextInt();
			this.redPoints.add(new Point(a, b));
		}
		this.bluePoints = new ArrayList<>(N);
		for (int i = 0; i < N; ++i) {
			int c = in.nextInt();
			int d = in.nextInt();
			this.bluePoints.add(new Point(c, d));
		}
		in.close();
		Collections.sort(this.redPoints, this.compX);
		Collections.sort(this.bluePoints, this.compX);
		this.redUsed = new boolean[N];
		Arrays.fill(this.redUsed, false);
	}

	int result = 0;

	void calc() {
		for (int i = 0; i < N; ++i) {
			Point bluePoint = this.bluePoints.get(i);
			int redPointIndex = findPair(bluePoint);
			if (redPointIndex >= 0) {
				result++;
				redUsed[redPointIndex] = true;
			}
		}
	}

	int findPair(Point bluePoint) {
		Set<Integer> redPointIndexes = new HashSet<>();
		for (int i = 0; i < N; ++i) {
			if (this.redPoints.get(i).getX() < bluePoint.getX() && this.redPoints.get(i).getY() < bluePoint.getY()) {
				if (!this.redUsed[i]) {
					redPointIndexes.add(i);
				}
			}
		}
		int result = -1;
		int yVal = Integer.MIN_VALUE;
		for (Integer i : redPointIndexes) {
			if (redPoints.get(i).y > yVal) {
				result = i;
				yVal = redPoints.get(i).y;
			}
		}

		return result;
	}

	public static void main(String[] args) {
		Main ins = new Main();
		ins.calc();
		System.out.println(ins.result);
	}
}

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

int main() {
  int a, b, c, d;
  cin >> a >> b >> c >> d;

  if (a + b > c + d) {
    cout << "Left";
  } 
  
  else if (a + b < c + d) {
    cout << "Right";
  } 
  
  else {
      cout << "Balanced";
    }
  
    
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
    int s;
    cin>>s;
    int h,m,ss;
    h=s/3600;
    s=s-h*3600;
    m=s/60;
    ss=s-m*60;
    cout<<h<<":"<<m<<":"<<ss<<endl;
    return 0;
}



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

using namespace std;

vector<int> get_divisors (int n) {
  vector<int> v;
  for (int i = 1; i <= sqrt(n); i++) {
    if (n % i == 0) {
      int I = n / i;

      v.push_back(i);
      if (i != I) v.push_back(I);
    }
  }
  return v;
}

int gcd (int a, int b) {
  return (b == 0) ? a : gcd(b, a % b);
}

int main () {
  int A, B, K;
  cin >> A >> B >> K;

  vector<int> cd = get_divisors(gcd(A, B));

  sort(cd.begin(), cd.end(), greater<int>());

  cout << cd.at(K - 1) << "\n";
}


Measured memory_bytes: 256
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define MOD (ll)(1e9+7)
#define INF 1e17
#define int ll
#define EPS (1e-6)
using namespace std;
using ll=long long;
using pii=pair<int,int>;

int gcd(int a,int b) { return b==0?a:gcd(b,a%b); }
int lcm(int a,int b) { return a/gcd(a,b)*b; }

int fpow(int b,int p)
{
	if(p==0) return 1;
	int h=fpow(b,p/2);
	if(p%2) return h*b%MOD*h%MOD;
	return h*h%MOD;
}

struct Cake{
	int x,y,z;
};

int a,b,c;
bool operator<(Cake x,Cake y){
	return x.x*a+x.y*b+x.z*c<y.x*a+y.y*b+y.z*c;
}
int get(vector<Cake> &v,int m){
	priority_queue<Cake> pq;
	for(auto &i:v) pq.push(i);
	Cake ans;
	ans.x=0; ans.y=0; ans.z=0;
	For(i,0,m-1){
		ans.x+=pq.top().x;
		ans.y+=pq.top().y;
		ans.z+=pq.top().z;
		pq.pop();
	}
	return abs(ans.x)+abs(ans.y)+abs(ans.z);
}

int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n,m; cin>>n>>m;
	vector<Cake> v(n);
	for(auto &i:v) cin>>i.x>>i.y>>i.z;
	int d[2]={-1,1};
	int ans=0;
	For(i,0,1) For(j,0,1) For(k,0,1){
		a=d[i]; b=d[j]; c=d[k];
		ans=max(ans,get(v,m));
	}
	cout<<ans<<"\n";
	return 0;
}





























Measured memory_bytes: 384
#include <stdio.h>

int main(void){
	int h, w;
	int i, j;

	while(1){
		scanf("%d %d ", &h, &w);	/* H??¨W?????\??? */
		if(h==0&&w==0)break;		/* H??¨W????????????0??????????????¢?????????????????? */
		for(i=0;i<h;i++){			/* ???H????????? */
			for(j=0;j<w;j++){		/* ?¨?W????????? */
				printf("#");		/* H??W?????§????????§#????????? */
			}
			printf("\n");
		}
		printf("\n");
	}

	return 0;
}

Measured memory_bytes: 576
def euclid(a,b):
	c=0
	if (a-b)<0:
		c=a
		a=b
		b=c
	r=-1
	while r!=0:
		r=a%b
		a=b
		b=r
	return a

A,B,C,D=map(int,input().split())
c1=(A-1)//C
d1=(A-1)//D
c2=B//C
d2=B//D
k=euclid(C,D)
CD=C*D//k
cd1=(A-1)//CD
cd2=B//CD
c3=c2-c1
d3=d2-d1
cd3=cd2-cd1
print(B-A+1-c3-d3+cd3)

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

#define mp make_pair
#define fi first
#define se second
#define pb push_back

typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ii,int> iii;
typedef pair<ll,ll> pll;

const int N = 2e5+5;
const ll INF = 1e18;
ll n, m, k;
ll A[N], B[N];

bool can(ll x)
{
    for (int i = 0; i <= x; i++)
    {
        int j = x-i;
        if (i <= n && j <= m && A[i]+B[j] <= k)
            return 1;
    }
    return 0;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        A[i] = A[i-1] + x;
    }
    for (int i = 1; i <= m; i++)
    {
        int x;
        cin >> x;
        B[i] = B[i-1] + x;
    }
    ll ans = 0;
    ll l = 0;
    ll r = n+m;
    while (l <= r)
    {
        ll m = (l+r) / 2;
        if (can(m))
        {
            l = m+1;
            ans = m;
        }
        else
            r = m-1;
    }
    cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 6748
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rrep(i,n) for(int i=(int)(n-1);i>=0;i--)
#define all(x) (x).begin(),(x).end()
#define sz(x) int(x.size())
#define get_unique(x) x.erase(std::unique(all(x)), x.end());
typedef long long ll;
const int INF = 1e9;
const ll MOD = 1e9+7;
const ll LINF = 1e18;
const double PI=acos(-1);
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

int main() {
    int n;
    string s,t;
    cin>>n>>s>>t;
    rep(i,n) cout<<s[i]<<t[i];
    cout<<endl;
}

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

int main()
{
    int n;
    cin >> n;
    vector<char> v(n);
    rep(i, n) cin >> v[i];
    int i = 0, j = n-1;
    int count = 0;
    while (i <= j) {
        while (v[i] == 'R') i++;
        while (v[j] == 'W') j--;
        if (i < j) {
            count++;
            i++;
            j--;
        }
        if (i == j) {
            count++;
            break;
        }
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 3624
#include <iostream>
#include <cstdio>
#include <cstring>
#include <climits>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <sstream>
#include <numeric>
// #include <boost/multiprecision/cpp_dec_float.hpp>
// #include <boost/multiprecision/cpp_int.hpp>

///////////////////////////////////////////////////////////////
// namespace
///////////////////////////////////////////////////////////////
using namespace std;
// namespace mp = boost::multiprecision;

///////////////////////////////////////////////////////////////
// types
///////////////////////////////////////////////////////////////
using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
// using mpi = mp::cpp_int;
// using mpf = mp::number<mp::cpp_dec_float<1024>>;

///////////////////////////////////////////////////////////////
// mod https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a
///////////////////////////////////////////////////////////////
// ll MOD = 1000000007;
//
// ll mod(long long val) {
//     long long res = val % MOD;
//     if (res < 0) res += MOD;
//     return res;
// }
//
// ll modinv(ll a) {
//     ll b = MOD, u = 1, v = 0;
//     while (b) {
//         ll t = a / b;
//         a -= t * b; swap(a, b);
//         u -= t * v; swap(u, v);
//     }
//     u %= MOD;
//     if (u < 0) u += MOD;
//     return u;
// }
//
// const int MAX = -1;
// ll fac[MAX], finv[MAX], inv[MAX];
// void com_init() {  // initialize nCk table with O(N)
//     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;
//     }
// }
// ll com(int n, int k){  // nCk
//     if (n < k) return 0;
//     if (n < 0 || k < 0) return 0;
//     return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
// }

struct P {ll a, b, c, d;};

int calc(const vector<ll > &curr, const vector<P> &v) {
    ll ret = 0;
    for (const auto &p: v) {
        if (curr[p.b] - curr[p.a] == p.c) ret += p.d;
    }
    return ret;
}

ll dfs(ll c, ll m, ll n, vector<ll> &curr, const vector<P> &v) {
    if (c == n) return calc(curr, v);
    ll i = (!curr.empty()) ? curr.back(): 1;
    ll ret = 0;
    for (ll j = i; j <= m; ++j) {
        curr.push_back(j);
        ret = max(ret, dfs(c + 1, m, n, curr, v));
        curr.pop_back();
    }
    return ret;
}


int main() {
    ll n, m, q; cin >> n >> m >> q;
    ll a, b, c, d;
    vector<P> v;
    for (ll i = 0; i < q; ++i) {
        cin >> a >> b >> c >> d; --a; --b;
        v.emplace_back(P{a, b, c, d});
    }
    vector<ll> curr;
    cout << dfs(0, m, n, curr, v) << endl;
    return 0;
}


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

using namespace std;

int main() {
  int n; cin >> n;
  vector<int> values;
  for (int i = 0; i < n; ++i) {
    int v; cin >> v;
    values.push_back(v);
  }
  vector<int> costs;
  for (int i = 0; i < n; ++i) {
    int c; cin >> c;
    costs.push_back(c);
  }
  
  vector<int> results;
  for (int i = 0; i < n; ++i) {
    results.push_back(values[i] - costs[i]);
  }
  
  int sum = 0;
  for (auto r : results) {
  	if (r > 0) {
    	sum += r;
    }
  }
  
  cout << sum << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int n;
vector<pair<long long, long long>> v;
long long memo[100000];
long long s(long long i) {
    if (i >= n) return 0;
    if (memo[i] >= 0) return memo[i];
    return memo[i] = max(
        s(i+1),
        1 + s(lower_bound(v.begin(), v.end(), make_pair(v[i].second, v[i].second)) - v.begin())
    );
}
int main () {
    cin >> n;
    for (int i = 0; i < n; i++) memo[i] = -1;
    for (int i = 0; i < n; i++) {
        int x, l;
        cin >> x >> l;
        v.push_back(make_pair(x-l, x+l));
    }
    sort(v.begin(), v.end());
    cout << s(0) << endl;
}

Measured memory_bytes: 5872
"""
N, Q = map(int, input().split())
nodes = [0 for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    nodes[b] = a

counter = [0 for _ in range(N+1)]
for _ in range(Q):
    p, x = map(int, input().split())
    counter[p] += x

for i in range(1, N+1):
    counter[i] += counter[nodes[i]]

print(' '.join(map(str, counter[1:])))
"""
from collections import deque
N, Q = map(int, input().split())
counter = [0 for _ in range(N+1)]
graph = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

for _ in range(Q):
    p, x = map(int, input().split())
    counter[p] += x

que = deque()
que.append(1)
checked = [False for _ in range(N+1)]

while(que):
    v = que.pop()
    checked[v] = True
    for u in graph[v]:
        if checked[u]:
            continue
        counter[u] += counter[v]
        que.append(u)

print(' '.join(map(str, counter[1:])))

Measured memory_bytes: 67164
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa == x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))

n,l = m()

k = [l+i for i in range(n)]

co = Max
for i in range(n):
    if abs(co) >= abs(k[i]):
        co = k[i]

print(sum(k) - co)

Measured memory_bytes: 38384
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>

using namespace std;

int main()
{
	int N, M, C;
	cin >> N >> M >> C;

	vector<int> B(M);
	for (int i = 0; i < M; i++)
	{
		cin >> B[i];
	}


	int ans = 0;
	for (int i = 0; i < N; i++)
	{
		int sum = 0;

		for (int k = 0; k < M; k++)
		{
			int a;
			cin >> a;
			sum += a * B[k];
		}
		sum += C;

		if (sum > 0)
		{
			ans++;
		}
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
while True:
    n,x=(int(l) for l in input().split())
    if n==0 and x==0:
        break
    answer_count=0
    for a in range(1,n+1):
        for b in range(1,a):
            for c in range(1,b):
                if a+b+c==x:
                    answer_count+=1
    print(answer_count)


Measured memory_bytes: 5600
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }
template<class T> ostream& operator << (ostream& out,const vector<T> V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }
template<class T> ostream& operator << (ostream& out,const vector<vector<T> > Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }
template<class S,class T> ostream& operator << (ostream& out,const map<S,T> mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }

/*
 <url:http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2011>
 問題文============================================================
 =================================================================
 解説=============================================================
 ================================================================
 */

int n;
ll solve(){
    ll res = -1;
    vector<vector<int>> schedule(31);
    for(int i = 0; i < n;i++){
        int f; cin >> f;
        for(int j = 0; j < f; j++){
            int d; cin >> d;
            schedule[d].push_back(i);
        }
    }
    
    vector<ll> maps(n);
    for(int i = 0; i < n;i++){
        maps[i] = (1LL<<i);
    }
    for(int i = 1; i <= 30; i++){
        int sz = (int)schedule[i].size();
        ll S = 0;
        for(int j = 0; j < sz;j++){
            S |= (maps[schedule[i][j]]);
        }
        for(int j = 0; j < sz;j++){
            maps[schedule[i][j]] |= S;
            if(maps[schedule[i][j]] == (1LL<<n)-1){
                res = i;
                break;
            }
        }
        if(res != -1) break;
    }
    return res;
}
int main(void) {
    cin.tie(0); ios_base::sync_with_stdio(false);
    while(cin >> n,n){
        cout << solve() << endl;
    }
    return 0;
}



Measured memory_bytes: 3224
#include <bits/stdc++.h>
#define maxn 23333333
#define mod 1000000007
using namespace std;
int f[maxn];

long long Pow (long long x, long long p) {
	long long ret = 1;
	for(; p; p >>= 1, x = x * x % mod) if(p & 1) ret = ret * x % mod; 
	return ret;
}

int main() {
	for(int i = 1; i < maxn; ++i) f[i] = f[i / 10] + 1;
	int S;
	scanf("%d", &S);
	long long ans = S >> 3;
	{
		int l, r, s, li = maxn;
		if(S % 8 == 0) li = 9999999 + S / 8;
		for(l = r = 1, s = f[r]; r < li; s += f[++r]) {
			while(s > S) s -= f[l++];
			if(s == S) ++ans;
		}
	}
//	cerr << ans << endl;
	for(int i = 1; i <= (S >> 3); ++i) {
		if(S % i == 0) {
			ans += 9 * Pow(10, S / i - 1) + mod - i;
		}
	}
	ans %= mod;
	printf("%lld", ans);
	return 0;
}

Measured memory_bytes: 94980
#include <bits/stdc++.h>
using namespace std;
using vi=vector<int>;
using vvi=vector<vi>;
using vs=vector<string>;
using msi=map<string,int>;
#define rep(i,n) for(int i=0;i<n;i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()

int main(void){
    int n,a,b;
    while(cin>>n>>a>>b,n){
        vi s(n);
        int ans=-1,t=-1;
        rep(i,n){
            cin>>s[i];
            if(a<=i && i<=b && t<=s[i-1]-s[i]){
                t=s[i-1]-s[i];
                ans=i;
            }
        }
        cout<<ans<<endl;
    }
}

Measured memory_bytes: 3052
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
#define rep(i,a,n) for(int i=a;i<n;++i)
#define per(i,a,n) for(int i=n-1;i>=a;--i)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define sz(x) ((int)x.size())
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
const ll mod=1000000007; // 998244353 = (119<<23)+1
ll powmod(ll a,ll b) {ll res=1;a%=mod;assert(b>=0);for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
// head
const int N=2e5+5;
vi tel(N);
bool vis[N];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	ll k;
	cin>>n>>k;
	rep(i,0,n) cin>>tel[i+1];
	int cur=1;
	while(k>0&&vis[cur]==false) {
		vis[cur]=true;
		k--;
		cur=tel[cur];
	}
	if(k==0) cout<<cur;
	else {
		ll len=1;
		int nxt=tel[cur];
		while(nxt!=cur) nxt=tel[nxt],len++;
		k%=len;
		rep(i,0,k) cur=tel[cur];
		cout<<cur;
	}
	return 0;
}

Measured memory_bytes: 4340
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<queue>

using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vector<int> >;
using pii = pair<int, int>;
using ppi = pair<pii, int>;

#define MOD 998244353

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int ti = clock();
  // start-----------------------------------------------
  int n, k; cin >> n >> k;
  vector<pii> usable(k);
  for(int i = 0; i < k; i++){
    int a, b;
    cin >> a >> b;
    usable[i] = {a, b};
  }
  vector<ll> addField(n+2, 0);
  vector<ll> field(n+2, 0);
  field[1] = 1;
  for(int i = 1; i <= n; i++){
    addField[i] += addField[i-1];
    addField[i] %= MOD;
    field[i] += addField[i];
    field[i] %= MOD;
    for(int j = 0; j < k; j++){
      if(i + usable[j].first <= n){
        addField[i+usable[j].first] += field[i];
        addField[i+usable[j].first] %= MOD;
        addField[min(i + usable[j].second + 1, n+1)] -= field[i];
        addField[min(i + usable[j].second + 1, n+1)] %= MOD;
      }
    }
    // for(int l = 1; l <= n; l++){
    //   cout << addField[l] << endl;;
    // }
    // cout << endl;
  }
  // for(int i = 1; i <= n; i++) cout << field[i] << endl;
  cout << (field[n] + MOD) % MOD << endl;

  // end-----------------------------------------------
  // cerr << 1.0 * (clock() - ti) / CLOCKS_PER_SEC << endl;
}


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

#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v),end()
#define pb push_back
typedef long long ll;
typedef pair<int,int> P;

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

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

    while(true)
    {
	int n,m;
	cin>>n;
	if(n==0) break;

	bool f[21][21]={0};
	REP(i,n){
	    int x,y;
	    cin>>x>>y;
	    f[x][y]=true;
	}

	cin>>m;
	int cnt=0;
	int x=10,y=10;
	REP(i,m){
	    char d; int l;
	    cin>>d>>l;
	    REP(j,l){
		if(d=='N') y++;
		else if(d=='E') x++;
		else if(d=='S') y--;
		else x--;
		cnt+=f[x][y];
		f[x][y]=0;
	    }
	}
	if(cnt==n) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
    }

}

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


int main()
{
    int n,t=0;
    cin >> n;
    if(n >= 500){
        t += n/500 * 1000;
        n = n%500;
    }

    if(n >= 5){
        t += n/5 * 5;
        n = n%5;
    }
    cout << t;


    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define BEGIN ios_base::sync_with_stdio(0);cin.tie(0)
#define END return EXIT_SUCCESS
#define FOR(I,A,B) for((I)=(A);(I)<(B);(I)++)
#define REP(I,N) FOR(I,0,N)
#define ALL(C) (C).begin(),(C).end()
#define INPUT(P) std::cin>>(P)
#define INPUT2(P1,P2) std::cin>>(P1)>>(P2)
#define INPUT3(P1,P2,P3) std::cin>>(P1)>>(P2)>>(P3)
#define INPUTS(I,N,V) REP(I,N) std::cin>>V[I]
#define OUTPUT(P) std::cout<<P<<std::endl
#define OUTPUT2(P1,P2) std::cout<<P1<<" "<<P2<<std::endl
#define OUTPUT3(P1,P2,P3) std::cout<<P1<<" "<<P2<<" "<<P3<<std::endl
#define OUTPUTS(I,N,V) REP(I,N) std::cout<<V[i]<<std::endl
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ul;
const int MOD = 1000000007;
const ll INF = 1e18;
const int MAX_N=100001;
using namespace std;
int i,j,k;
int n;
int t;
int v[MAX_N];
int c[6];
int even_cnt[MAX_N];
int odd_cnt[MAX_N];
inline void solve(){
  INPUT(n);
  REP(i,n){
    cin>>v[i];
    if(i&1)even_cnt[v[i]]++;
    else odd_cnt[v[i]]++;
  }
  REP(i,MAX_N){
    if(c[2]<even_cnt[i]){
      c[3]=c[2];
      c[2]=even_cnt[i];
      c[4]=i;
    }else if(c[3]<even_cnt[i]){
      c[3]=even_cnt[i];
    }
    if(c[0]<odd_cnt[i]){
      c[1]=c[0];
      c[0]=odd_cnt[i];
      c[5]=i;
    }else if(c[1]<odd_cnt[i]){
      c[1]=odd_cnt[i];
    }
  }
  if(c[4]!=c[5])OUTPUT(n-c[0]-c[2]);
  else OUTPUT(min(n-c[0]-c[3],n-c[1]-c[2]));
}

int main(int argc,char**argv){
  BEGIN;
  solve();
  END;
}


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

#define lli long long int
#define REP(i,s,n) for(int i=s;i<n;i++)
#define NUM 2520
#define INF (1LL<<50)
#define DEBUG 0
#define mp(a,b) make_pair(a,b)
#define SORT(V) sort(V.begin(),V.end())
#define PI (3.141592653589794)
#define TO_STRING(VariableName) # VariableName
#define LOG(x) if(DEBUG)cout<<TO_STRING(x)<<"="<<x<<" "<<endl;
#define LOG2(x,y) if(DEBUG)cout<<TO_STRING(x)<<"="<<x<<" "<<TO_STRING(y)<<"="<<y<<endl;
#define LOG3(x,y,z) if(DEBUG)cout<<TO_STRING(x)<<"="<<x<<" "<<TO_STRING(y)<<"="<<y<<" "<<TO_STRING(z)<<"="<<z<<endl;

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

lli data[900][900];
bool vis[900][900];

int main(){

	lli h,w,k;
	cin>>h>>w>>k;

	lli si,sj;
	REP(i,0,h)REP(j,0,w){
		char tmp;
		cin>>tmp;
		if(tmp=='#')data[i][j]=-1;
		else if(tmp=='S')si=i,sj=j;
	}

	queue<lli> qi,qj;
	queue<lli> qd;
	qi.push(si);
	qj.push(sj);
	qd.push(0);
	vis[si][sj]=true;


	while(qi.size()){
		lli topI = qi.front();
		lli topJ = qj.front();
		qi.pop(),qj.pop();
		lli topD = qd.front();
		qd.pop();
		data[topI][topJ]=1;

		if(topD>=k)continue;

		lli di[4]={-1,0,1,0};
		lli dj[4]={0,1,0,-1};

		REP(i,0,4){
			lli nextI = topI + di[i];
			lli nextJ = topJ + dj[i];
			if(nextI<0 || nextI>=h || nextJ<0 || nextJ>=w)continue;
			if(data[nextI][nextJ]<0)continue;
			if(vis[nextI][nextJ])continue;

			vis[nextI][nextJ]=true;
			qi.push(nextI);
			qj.push(nextJ);
			qd.push(topD+1);
		}
	}

	lli ans = INF;

	REP(i,0,h)REP(j,0,w){
		if(data[i][j]==1){
			lli length = min({i,j,(int)h-1-i,(int)w-1-j});
			if(length==0){
				cout<<1<<endl;
				return 0;
			}
			ans = min(ans,(length-1)/k+2);
		}
	}
	cout<<ans<<endl;

}

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

    int a[32] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
    int main() {
      int k;
      cin >> k;
      cout << a[k - 1] << endl;
    }

Measured memory_bytes: 256
from collections import deque

def main():
  def p(a,b):
    if a < b:
      return (a,b)
    else:
      return (b,a)
  #input = open(0).readline
  N = int(input())
  E = [[] for i in range(N)]
  C = {}
  D = [0] * N
  parent = [0]*N
  for i in range(N-1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    E[a].append(b)
    E[b].append(a)
    C[p(a,b)] = c

  M, K = map(int, input().split())
  K -= 1
  parent[K] = K
  Q = deque()
  Q.append(K)

  while Q:
    u = Q.popleft()
    d = D[u]
    for v in E[u]:
      if parent[u] == v:
        continue
      parent[v] = u
      D[v] = d + C[p(u,v)]
      Q.append(v)

  for i in range(M):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    print(D[x]+D[y])

main()
  
 

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

int main() {
  int n;
  vector<string> s(n);
  int c = 0;
  cin >> n;
  for (int i = 0; i < n; i++)
  {
    cin >> s.at(i);
  }
  for (int i = 0; i < n; i++){
    if (s.at(i) == "Y")
    {
      c = 1;
      break;
    }
  }

  if (c) 
    cout << "Four" << endl;
  else
    cout << "Three" << endl;
  
  return 0;
}

Measured memory_bytes: 3872
#include <bits/stdc++.h>
using namespace std;
int main(void){
   long long int data[100002],cmp[100002];
   long long int a,n,count=0;
   cin >> n;
   for(int i=0;i<n;i++){
       cin >> a;
       if(a>100000){
           count++;
           
       }
       else{cmp[a-1]=a;
       data[a-1]+=1;
       }
   }
   for(long long int i=0;i<100000;i++){
        
       if(cmp[i]!=data[i]){
            
          for(int j=0;j<100000;j++){
              if(cmp[i]==data[i] || data[i]==0){
                  break;
              }
              data[i]--;
              count++;
          }
         
       }
       
   }
   cout << count << endl;
    return 0;
}


Measured memory_bytes: 384
import itertools

n, m = map(int, input().split())
graph = [[0 for i in range(n)] for j in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    graph[a - 1][b - 1] = 1
    graph[b - 1][a - 1] = 1
ans = 0
for i in itertools.permutations(range(2, n + 1)):
    if not graph[0][i[0] - 1]:
        continue
    for j in range(n - 1):
        if j == n - 2:
            ans += 1
            break
        if not graph[i[j] - 1][i[j + 1] - 1]:
            break
print(ans)

Measured memory_bytes: 3064
//#pragma GCC target("avx2")
//#pragma GCC optimize("O3")
 
//#include <x86intrin.h>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <bitset> 
#include <vector>
#include <cmath>
#include <deque>
#include <queue>
#include <iomanip>
#include <stack>
#include <map>
#include <set>
//#include <ordered_set>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
 
//using namespace __gnu_pbds;
using namespace std;
 
//template<typename T> using ordered_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
     
#define F first
#define S second           
#define lb lower_bound               
#define ub upper_bound
#define pb push_back
#define pf push_front    
#define ppb pop_back
#define mp make_pair                                     
#define bpp __builtin_popcountll                                                                                        
#define sqr(x) ((x) * (x)) 
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define in insert
#define ppf pop_front
#define endl '\n'
//#define int long long
 
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
 
const int mod = 998244353;
const int N = (int)3e5 + 123;
const ll inf = (ll)1e18 + 1;
 
const double pi = acos (-1.0);
const double eps = 1e-9;                  
const int dx[] = {0, 0, 1, 0, -1};
const int dy[] = {0, 1, 0, -1, 0};

int n, s, a[3003], dp[3003][3003], ans;

inline int add (int a, int b) {
   a += b;
   if (a >= mod) a -= mod;
   if (a < 0) a += mod;
   return a;
}

inline void boost () {
   ios_base :: sync_with_stdio (0);
   cin.tie (0), cout.tie (0);
}
 
inline void Solve () {
   cin >> n >> s;
   for (int i = 1; i <= n; i ++) cin >> a[i];    
   dp[0][0] = 1;
   for (int i = 1; i <= n; i ++) {
      for (int j = 0; j <= s; j ++) {
         dp[i][j] = add (dp[i][j], dp[i - 1][j] + (j == 0));
         if (j >= a[i]) dp[i][j] = add (dp[i][j], dp[i - 1][j - a[i]]);
      }
      ans = add (ans, dp[i][s]);
   }
   cout << ans;
}               
 
signed main () {                                       
   //#ifdef QWERTY
   //   freopen("input", "r", stdin);
   //#endif
// freopen (".in", "r", stdin);    
// freopen (".out", "w", stdout);              
   boost ();
   int tt = 1;
   //cin >> tt;   
   while (tt --) {
      Solve ();
   }                                               
   return 0;      
}                   

Measured memory_bytes: 35456