akhauriyash/Code-Regression huggingface dataset:
n = int(input())
*arr, = map(int, input().split())
arr.sort(reverse=True)


circle = [arr[0]]

s = 0

i = 1
UNDEF = -1
while len(circle) != len(arr):
    new_circle = []
    for v in circle:
        new_circle.append(v)
        new_circle.append(UNDEF)
    circle = new_circle
    positions = list(range(1, len(circle), 2))
    weights = [UNDEF] * len(circle)
    for pos in positions:
        weights[pos] = min(circle[(pos - 1) % len(circle)], circle[(pos + 1) % len(circle)])

    positions.sort(key=lambda pos: weights[pos], reverse=True)
    # print(circle)
    # print(positions)
    # print(weights)
    j = 0
    while i < len(arr) and j < len(positions):
        circle[positions[j]] = arr[i]
        w = weights[positions[j]]
        i += 1
        j += 1
        s += w
    circle = [v for v in circle if v != UNDEF]

print(s)


Measured memory_bytes: 134404
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* constant */

#define MAX_M           (10)
#define MAX_N           (10)
#define MAX_HOME        (23)

/* typedef */

typedef int nbr_t[MAX_HOME + 1];

/* global variables */

static int m, n;
static int nhome;

static int toch[MAX_HOME], visited[MAX_HOME];
static nbr_t nbrs[MAX_HOME][4];

static int drcs[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

/* subroutines */

void find_nbr(int y0, int x0, int sects[], nbr_t *nbr) {
  int dx, dy, hid, i, j, x, y;

  for (i = 0; i < 4; i++) {
    dy = drcs[i][0];
    dx = drcs[i][1];
    y = y0 + dy;
    x = x0 + dx;
    j = 0;

    while (y >= 0 && y < n && x >= 0 && x < m) {
      hid = sects[y * m + x];
      if (hid != -1) nbr[i][j++] = hid;
      y += dy;
      x += dx;
    }

    nbr[i][j] = -1;
  }
}

int count_rt(int k, int hid) {
  int count, i;
  int *nb0;

  if (k == 0)
    return (toch[hid] ? 1 : 0);

  count = 0;

  for (i = 0; i < 4; i++) {
    for (nb0 = nbrs[hid][i]; *nb0 != -1; nb0++) {
      if (! visited[*nb0]) {
        visited[*nb0] = 1;
        count += count_rt(k - 1, *nb0);
        visited[*nb0] = 0;
        break;
      }
    }
  }

  return count;
}

/* main */

int main(int argc, char **argv) {
  int chx, chy, count, d, hid, i, *nb0, x, y;
  static int homes[MAX_HOME][2];
  static int sects[MAX_N * MAX_M];
  static nbr_t fromch[4];

  for (;;) {
    scanf("%d %d", &m, &n);
    if ((m | n) == 0) break;

    nhome = 0;

    for (y = 0; y < n; y++) {
      for (x = 0; x < m; x++) {
        scanf("%d", &d);

        switch (d) {
        case 1:
          homes[nhome][0] = y;
          homes[nhome][1] = x;
          sects[y * m + x] = nhome++;
          break;
        case 2:
          chy = y;
          chx = x;
        default:
          sects[y * m + x] = -1;
        }
      }
    }

    find_nbr(chy, chx, sects, fromch);

    memset(toch, 0, sizeof(int) * nhome);

    for (i = 0; i < 4; i++)
      for (nb0 = fromch[i]; *nb0 != -1; nb0++)
        toch[*nb0] = 1;

    for (i = 0; i < nhome; i++)
      find_nbr(homes[i][0], homes[i][1], sects, nbrs[i]);

    memset(visited, 0, sizeof(int) * nhome);

    count = 0;

    for (i = 0; i < 4; i++) {
      hid = *(fromch[i]);
      if (hid != -1) {
        visited[hid] = 1;
        count += count_rt(nhome - 1, hid);
        visited[hid] = 0;
      }
    }

    printf("%d\n", count);
  }

  return 0;
}

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


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

Measured memory_bytes: 3088
#include <bits/stdc++.h>
using namespace std;
char s[20];
int nn[20];
unordered_map<long long, long long> dp[20][150][3];
__inline int upd(int b, int d, int x) {
	if (b == 0) return 0;
	if (b == 2) return 2;
	if (d < x) return 0;
	if (d == x) return 1;
	return 2;
}
int main() {
	scanf("%s", s + 1);
	int n = (int) strlen(s + 1);
	for (int i = 1; i <= n; ++ i) nn[i] = s[i] - '0';
	dp[0][0][1][1] = 1;
	for (int i = 1; i <= n; ++ i) {
		for (int d = 0; d <= 9; ++ d) {
			for (int a = 0; a <= i * 9; ++ a) {
				for (int b = 0; b <= 2; ++ b) {
					for (auto x : dp[i - 1][a][b]) {
						dp[i][a + d][upd(b, d, nn[i])][x.first * (d + 1)] += x.second;
					}
				}
			}
		}
	}
	int S = 0;
	long long M = 1;
	for (int i = 1; i <= n; ++ i) {
		S += nn[i];
		M = M * (1 + nn[i]);
	}
	long long ans = 0;
	for (int i = 0; i <= S - 1; ++ i) {
		for (int b = 0; b <= 2; ++ b) {
			for (auto x : dp[n][i][b]) ans += x.second;
		}
	}
	for (int b = 0; b <= 2; ++ b)
	for (auto x : dp[n][S][b]) if (x.first < M) ans += x.second;
	for (auto x : dp[n][S][0]) if (x.first == M) ans += x.second;
	printf("%lld\n", ans);
}

Measured memory_bytes: 52036
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N, M = map(int, input().split())
X, Y, Z = [0] * N, [0] * N, [0] * N

for i in range(N):
    X[i], Y[i], Z[i] = map(int, input().split())

codes = [[1, 1, 1], [1, 1, -1], [1, -1, 1], [1, -1, -1], [-1, 1, 1], [-1, 1, -1], [-1, -1, 1], [-1, -1, -1]]


def calc(code, idx):
    return code[0] * X[idx] + code[1] * Y[idx] + code[2] * Z[idx]


INF = 1 << 60
ans = -INF
for code in codes:
    ar = [0] * N

    for i in range(N):
        ar[i] = calc(code, i)

    ar.sort(reverse=True)

    ans = max(ans, sum(ar[:M]))

print(ans)

Measured memory_bytes: 40964
#include "bits/stdc++.h"
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
const double EPS = 1e-9;
#define INF (1LL<<60)
#define D double
#define fs first
#define sc second
#define int long long
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define RFOR(i,a,b) for(int i = (int)(b-1);i>=(int)(a);--i)
#define REP(i,n)  FOR(i,0,(n))
#define RREP(i,n) RFOR(i,0,(n))
#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
#define RITR(itr,mp) for(auto itr = (mp).rbegin(); itr != (mp).rend(); ++itr)
#define range(i,a,b) ((a)<=(i) && (i)<(b))
#define debug(x)  cout << #x << " = " << (x) << endl;
#define SP << " " << 
typedef pair<int,int> P;
typedef vector<int> vec;
typedef vector<vector<int>> mat;

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

  int n;
  string s;
  cin >> n >> s;

  int p = 0;
  int need_left = 0;

  REP(i, s.length()){
    if(s[i] == '('){
      p++;
    }
    else{
      if(p == 0) need_left++;
      else p--;
    }
  }
  int need_right = p;

  REP(i, need_left) cout << '(';
  cout << s;
  REP(i, need_right) cout << ')';
  cout << endl;

  return 0;
}

Measured memory_bytes: 256
//“Make it work, make it right, make it fast.” – Kent Beck
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double dd;
const int siz = 1e6 + 5;
const int MOD = 1e9 + 7;
#define endl '\n'
#define deb(x) cout << #x << " = " << x << endl;
void solve(){
	int n;
	cin >> n;
	int a[n];
	for(int &i : a) cin >> i;
	ll ans = 0, mini = INT_MAX;
	for(int i = 0; i <= 100; i++){
		ans = 0;
		for(int j = 0; j < n; j++){
			ans += (a[j]-i) *(a[j]-i);
		}
		mini = min(mini, ans);
	}
	cout << mini << endl;
}

int main(){
	#ifndef RAY
		//freopen("input.txt", "r", stdin);
	#endif
		ios::sync_with_stdio(false);
		cin.tie(nullptr);
		int t = 1;
		//cin >> t;
		while(t--){
			solve();
		}
	return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int[] a = new int[55];
        for(int i = 1; i <= n; ++i){
            a[i] = input.nextInt();
        }
        int[][] b = new int[55][2];
        int sum = 0;
        for(int i = 1; i <= n; ++i){
            if(a[i] != i){
                b[sum][0] = i;
                b[sum][1] = a[i];
                sum++;
            }
        }
        if(sum <= 2) System.out.println("YES");
        else System.out.println("NO");
    }
}


Measured memory_bytes: 23764
// Problem : A - AC or WA
// Contest : AtCoder - AtCoder Beginner Contest 152
// URL : https://atcoder.jp/contests/abc152/tasks/abc152_a
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

//Macros

#define ll long long
#define db long double
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define mi map<int,int>
#define mii map<pii,int>
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
#define sz(x) (int)x.size()
#define mod 1000000007
#define EPS 1e-9
#define io ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define inf 1e10
#define PI acos(-1.0)
#define int long long
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define N 100005

//Solution

void solve(){
    int n,m;
    cin>>n>>m;
    if(n == m) cout<<"Yes\n";
    else cout<<"No\n";
}

signed main(){
    io;
    //freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
    int tests;
    //cin>>tests;
    tests = 1;
    while(tests--){
        solve();
    }
    return 0;
}

Measured memory_bytes: 3636
#include<bits/stdc++.h>
#define MOD (long long)(1e9+7)
using namespace std;
long long n,k,dp[105][100005],c[105];
int main()
{
	cin >> n >> k;
	dp[0][0]=1;
	for(int i=1; i<=n; i++)
	{
		cin >> c[i];
		long long sum=0;
		for(int j=0; j<=c[i]; j++)
		{
			sum+=dp[i-1][j];
			dp[i][j]=(dp[i][j]+sum)%MOD;
		}
		sum-=dp[i-1][0];
		for(int j=c[i]+1; j<=k; j++)
		{
			sum+=dp[i-1][j];
			dp[i][j]=(dp[i][j]+sum)%MOD;
			sum-=dp[i-1][j-c[i]];
		}
	}
	//for(int i=1; i<=n; cout<<'\n',i++)
	//	for(int j=0; j<=k; j++) cout << dp[i][j] << ' ';
	cout << dp[n][k];
	return 0;
}

Measured memory_bytes: 81772
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long
int mod=1e9+7;

signed main()
{

    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
	
  	ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n,k;
  cin>>n>>k;
  vector<int> v(n);
    for (int i=0;i<n;++i)
      cin>>v[i];
  int dp[n+1];
  dp[0]=0;
 	dp[1]=abs(v[1]-v[0]);
  for (int i=2;i<n;++i)
  {
    int ans=INT_MAX;
    for (int j=1;j<=k && i-j>=0 ;++j){
    	ans=min(abs(v[i]-v[i-j])+dp[i-j],ans);
    }
    dp[i]=ans;
  }
  cout<<dp[n-1]<<endl;


}


Measured memory_bytes: 4780
#include <iostream>
#include <cstdio>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <stack>
#include <utility>
#include <numeric>
#include <algorithm>
#include <functional>
#include <cctype>
#include <complex>
#include <string>
#include <sstream>

using namespace std;

#define all(c) c.begin(),c.end()
#define rall(c) c.rbegin(),c.rend()
#define mp(a,b) make_pair((a),(b))
#define eq ==

typedef long long ll;
typedef complex<double> point;
typedef pair<int,int> pii;

// →↑←↓
const int dx[] = {1,0,-1,0};
const int dy[] = {0,-1,0,1};


const double EPS = 1e-9;

int main(){
    // S A C
    const int M = 256;
//    vector<vector<vector<vector<int> > > >R(16,vector<vector<vector<int> > >(16,vector<vector<int> >(16,vector<int>(M+1))));
//    for(int s=0;s<=15;s++){
//        for(int a=0;a<=15;a++){
//            for(int c=0;c<=15;c++){
//                for(int i=0;i<=M;i++){
//                    if(i == 0){
//                        R[s][a][c][i] = s;
//                    }else{
//                        R[s][a][c][i] = (a*R[s][a][c][i-1]+c) % M;
//                    }
//                }
//            }
//        }
//    }

    while(true){
        int N;
        cin >> N;
        if(N == 0) break;
        vector<int> I(N);
        vector<int> O(N);
        vector<int> Ht(N+1);
        int ms,ma,mc;
        double mh = 100000000;
        for(int i=0;i<N;i++){
            cin >> I[i];
        }
        for(int s=0;s<=15;s++){
            for(int a=0;a<=15;a++){
                for(int c=0;c<=15;c++){
                    vector<int> num(M);
                    int R = s;
                    for(int i=0;i<N;i++){
                        R = (a*R+c) % M;
                        num[(I[i]+R) % M]++;
                    }
                    double H = 0;
                    for(int i=0;i<num.size();i++){
                        if(num[i] != 0){
                            H += -(1.0* num[i]/N * log(1.0*num[i]/N));
                        }
                    }
                    if(H+EPS < mh){
                        mh = H;
                        ms = s;ma = a;mc = c;
                    }
                }
            }
        }
        cout << ms << " " << ma << " " << mc << endl;
    }
    return 0;
}

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

int main()
{
	int a=0, b, c=0, x, y;
	cin >> x >> y;
	
	
	
	for (int i=0; i<=x; i++)
	{
		b=2*a+4*(x-a);
		if(b==y)
		{
			c++;
			cout << "Yes";
			break;
		}	
		else
		{
			a++;
			continue;
		}
	}
	if (c==0)
		cout << "No";
	return 0;
}

Measured memory_bytes: 3632
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String S = sc.next();

        System.out.println(solve(S) ? "Yes" : "No");

        sc.close();
    }

    static boolean solve(String S) {
        return S.chars().distinct().count() == 3;
    }
}

Measured memory_bytes: 29268
#include <bits/stdc++.h>
#define int long long
#define ll long long
using ull = unsigned long long;
using namespace std;
const int INF = 1e10;
const int MOD = 1e9 + 7;
#define dump(x)                             \
    if (dbg) {                              \
        cerr << #x << " = " << (x) << endl; \
    }
#define overload4(_1, _2, _3, _4, name, ...) name
#define FOR1(n) for (ll i = 0; i < (n); ++i)
#define FOR2(i, n) for (ll i = 0; i < (n); ++i)
#define FOR3(i, a, b) for (ll i = (a); i < (b); ++i)
#define FOR4(i, a, b, c) for (ll i = (a); i < (b); i += (c))
#define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define FORR(i, a, b) for (int i = (a); i <= (b); ++i)
template <class T>
bool chmin(T& a, const T& b) {
    if (a > b) {
        a = b;
        return 1;
    } else
        return 0;
}
template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return 1;
    } else
        return 0;
}
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(), (v).end()
#define SZ(x) ((int)(x).size())
#define P pair<int, int>
#define V vector<int>
//#define S set<int>
#define itn int
bool dbg = false;

int N, t[100];
string X, s[100];

void solve() {
    int ans = 0;
    FOR(N) {
        if (s[i] == X) {
            FOR(j, i + 1, N) {
                ans += t[j];
            }
            break;
        }
    }
    cout << ans << endl;
}

signed main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> N;
    FOR(N)
    cin >> s[i] >> t[i];
    cin >> X;
    solve();
    return 0;
}


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

using namespace std;

int main()
{
    int food[1001] = {0};
    int n, m, a[1001][1001];
    int k[1001];
    int ans = 0;

    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        cin >> k[i];

        for (int j = 0; j < k[i]; j++) {
            cin >> a[i][j];
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < k[i]; j++) {
            food[a[i][j]]++;
        }
    }

    for (int i = 0; i < 1001; i++) {
        if (food[i] == n) ans++;
    }

    cout << ans << endl;
}


Measured memory_bytes: 384
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <cctype>
#include <cstdlib>
using namespace std;
typedef long long lint;
#define cout cerr
#define ni (next_num<int>())
template<class T>inline T next_num(){
	T i=0;char c;
	while(!isdigit(c=getchar())&&c!='-');
	bool flag=c=='-';
	flag?c=getchar():0;
	while(i=i*10-'0'+c,isdigit(c=getchar()));
	return flag?-i:i;
}
template<class T1,class T2>inline void apmax(T1 &a,const T2 &b){if(a<b)a=b;}
template<class T1,class T2>inline void apmin(T1 &a,const T2 &b){if(b<a)a=b;}
const int N=100010;
namespace T{
	struct Node;
	typedef Node* node;
	struct Node{
		node lson,rson;
		int prior,len,size;
		lint a,d;
		inline void up(){
			size=len;
			if(lson){
				size+=lson->size;
			}
			if(rson){
				size+=rson->size;
			}
		}
	}*rt,pool[N<<1];
	inline void init(){
		memset(pool,0,sizeof(pool));
	}
	inline node nn(){
		static node n=pool-1;
		return n++,n->prior=rand(),n;
	}
	node merge(node u,node v){//u on left, v on right
		if(u==0||v==0){
			return u?u:v;
		}
		if(u->prior>v->prior){
			return u->rson=merge(u->rson,v),u->up(),u;
		}else{
			return v->lson=merge(u,v->lson),v->up(),v;
		}
	}
	inline ostream & operator << (ostream & out,node x){
		if(x==0)return out;
		out<<x->lson;
		if(x->d==-1){
			out<<"["<<x->a<<","<<x->a+x->d*(x->len-1)<<"]";
		}else{
			out<<"["<<x->a<<"](len="<<x->len<<")";
		}
		out<<"(size="<<x->size<<") ";
		out<<x->rson;
		return out;
	}
	node rootl,rootr;
	void split(node x,int size,node &l=rootl,node &r=rootr){
		if(x==0)return;
		int lsize=x->lson?x->lson->size:0;
		if(size<=lsize){
			node tmp=x->lson;
			r=x,x->size-=size;
			split(tmp,size,l,x->lson=0);
		}else if(size>=lsize+x->len){
			node tmp=x->rson;
			l=x,x->size=size;
			split(tmp,size-lsize-x->len,x->rson=0,r);
		}else{
			size-=lsize;
			node n=nn();
			n->rson=x->rson,x->rson=0;
			n->len=x->len-size,x->len=size;
			n->a=x->a+size*x->d,n->d=x->d;
			x->up(),n->up();
			l=x,r=n;
		}
	}
	lint getans(node x){
		lint ans=x->a+x->d*(x->len-1);
		if(x->lson){
			apmin(ans,getans(x->lson));
		}
		if(x->rson){
			apmin(ans,getans(x->rson));
		}
		return ans;
	}
}
int k;
inline lint Main(){
	int n=ni;
	k=ni;
	T::init();
	T::rt=T::nn();
	T::rt->len=T::rt->size=k;
	lint sum=0;
	for(int i=1;i<=n;i++){
		int a=ni,b=ni;
		sum+=a;
		using namespace T;
		rootl=rootr=0;
		if(b==1){//single way track
			if((a<<1)>k)return -1;
			split(rt,a<<1);
			node ch=rootl;
			for(;ch->rson;ch=ch->rson);
			lint val=ch->a+ch->d*(ch->len-1);
			node nd=nn();
			nd->len=rootl->size;
			nd->a=val+nd->len-1,nd->d=-1;
			nd->up();
			rt=merge(rootr,nd);
		}else{//two way track
			split(rt,(a<<1)%k);
			rt=merge(rootr,rootl);
		}
		assert(rt->size==k);
	}
	return (sum<<1)+T::getans(T::rt);
}
int main(){
	printf("%lld\n",Main());
	return 0;
}

Measured memory_bytes: 9600
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>
#include <fstream>
#include <bitset>
#include <time.h>
#include <tuple>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef complex<double> Point;

#define PI acos(-1.0)
#define EPS 1e-10
const ll INF = (1LL << 60) - 1;
const ll MOD = 1e9 + 7;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,N) for(int i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define EQ(a,b) (abs((a)-(b))<EPS)
#define EQV(a,b) ( EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()) )
#define fi first
#define se second
#define N_SIZE (1LL << 20)
#define NIL -1
#define MAX_N 100100 * 3

int n;
int ans = 0;

int main() {
	cin >> n;
	rep(i, n) {
		int l, r;
		cin >> l >> r;
		ans += (r - l + 1);
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
import sys


def input():
    return sys.stdin.readline().strip()


def main():
    N, X, Y = map(int, input().split())
    cnt = [0 for _ in range(N)]
    for i in range(1, N):
        for j in range(i + 1, N + 1):
            dis_ij = min(j - i, abs(X - i) + abs(Y - j) + 1)
            cnt[dis_ij] += 1
    for i in range(1, N):
        print(cnt[i])


if __name__ == "__main__":
    main()


Measured memory_bytes: 3572
#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
	return;
}
long long n,a,b;
long long ans=0;
int main()
{
    cin>>n>>a>>b;
    cout<<n/(a+b)*a+min(n%(a+b),a)<<endl;
	return 0;
}


Measured memory_bytes: 256
class Node
  attr_accessor :id, :children, :visited, :depth

  def initialize(id)
    @id = id
    @children = []
    @visited = false
    @depth = -1
  end

  def add_child(child)
    @children << child
  end

  def visit
    self.visited = true
  end

  def to_s
    "#{@id}"
  end

  def bfs
    self.depth = 0
    que = [self]
    self.visit
    while not que.empty?
      n = que.shift
      n.children.each do | c |
        c.depth = n.depth + 1 if c.depth == -1
        que << c unless c.visited
        c.visit
      end
    end
  end

end

n = gets.to_i
tree = Array.new(n+1){ | i | Node.new(i) }
tree[0] = nil

n.times do
  ukv = gets.split.map(&:to_i)
  u = ukv.shift; ukv.shift
  ukv.each do | v |
    tree[u].add_child(tree[v])
  end
end

tree[1].bfs

1.upto(n) do | i |
  puts "#{tree[i].id} #{tree[i].depth}"
end



Measured memory_bytes: 6892
n = gets.to_i
d, x = gets.split.map(&:to_i)
a = n.times.map{gets.to_i}
choco = 0
a.each do |i|
    if d % i == 0
        choco += (d / i)
    else
        choco += (d / i + 1)
    end
end
choco += x
puts choco

Measured memory_bytes: 3836
#include <bits/stdc++.h>
#define ll long long

using namespace std;

ll gcd(ll a, ll b){
	if(b==0)
		return a;
	else
		return gcd(b, a%b);
}

int main() {
	// your code goes here
	ll k, sum=0;
	cin >> k;
	for(ll i=1; i<=k; i++){
		for(ll j=1; j<=k; j++){
			for(ll l=1; l<=k; l++){
				sum+=gcd(gcd(i, j), l);
			}
		}
	}
	cout << sum << endl;
	return 0;
}

Measured memory_bytes: 3528
N = int(input())
st = []
for i in range(N):
    st.append(list(map(str, input().split())))
X = input()

ans = 0
flag = 0
for s,t in st:
    if not flag:
        if s == X:
            flag = 1
    else:
        ans += int(t)
print(ans)

Measured memory_bytes: 38428
#include <stdio.h>
int main(void){
    // Your code here!
    int N,M,C,A,B[20],count=0;
    scanf("%d",&N);
    scanf("%d",&M);
    scanf("%d",&C);
    for(int i = 0; i < M; i++)
        scanf("%d",&B[i]);
        
    for(int i = 0; i < N; i++)
    {
        int sum = C;
        for(int j = 0; j < M; j++)
        {
            scanf("%d",&A);
            sum += A*B[j];
        }
        if(sum > 0)
            count++;
    }
    
    printf("%d\n",count);
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int a,b;
int main()
{
	cin>>a>>b;
	int c=abs(a-b);
	if(c%2)
	{
		cout<<"IMPOSSIBLE";
		return 0;
	}
	c/=2;
	c+=min(a,b);
	cout<<c;
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <cmath>   
#include<cctype>
#include<string>
#include<set>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include <deque>
#include <climits>
#include <typeinfo>
#include <utility> 
#define all(x) (x).begin(),(x).end()
#define rep(i,m,n) for(int i = m;i < n;++i)
#define pb push_back
#define fore(i,a) for(auto &i:a)
#define rrep(i,m,n) for(int i = m;i >= n;--i)
#define INF INT_MAX/2
using namespace std;
using ll = long long;
using R = double;
const ll inf = 1LL << 50;
const ll MOD = 1e9 + 7;
struct edge { ll from; ll to; ll cost; };


ll dp[110][5][5][5];

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

	dp[0][0][0][0] = 1;

	rep(i, 0, n)rep(j, 0, 5)rep(k, 0, 5)rep(l,0,5){
		if (i == 0 && (j != 0 || k != 0 || l != 0))continue;
		if (i == 1 && (j == 0 || k != 0 || l != 0))continue;
		if (i == 2 && (j == 0 || k == 0 || l != 0))continue;
		if (i >= 3 && (j == 0 || k == 0 || l == 0))continue;
		rep(m, 1, 5) {
			int c1 = ((k == 1) && (j == 2) && (m == 3));
			int c2 = ((k == 1)&&(j == 3)&&(m == 2));
			int c3 = ((k == 2)&&(j == 1)&&(m == 3));
			int c4 = ((l == 1) && (j == 2) && (m == 3));
			int c5 = ((l == 1) && (k == 2) && (m == 3));
			if (!c1 && !c2 && !c3 && !c4 && !c5) {
				dp[i + 1][m][j][k] += dp[i][j][k][l]%MOD;
				dp[i + 1][m][j][k] %= MOD;
			}
		}
	}

	ll ans = 0;
	rep(j, 1, 5)rep(k, 1, 5)rep(l,1,5){
		ans += dp[n][j][k][l];
		ans %= MOD;
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 384
def cmb(n, r, MOD):
    # nCr = a/b
    a, b = 1, 1
    for i in range(r):
        a = a * (n - i) % MOD
        b = b * (i + 1) % MOD
    return a * pow(b, MOD - 2, MOD)

MOD = 10**9 + 7
n, a, b = list(map(int, input().split()))
ans = pow(2, n, MOD) - 1 - cmb(n, a, MOD) - cmb(n, b, MOD)
print(ans % MOD)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define fastIO (cin.tie(0), cout.tie(0), ios::sync_with_stdio(false))
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define precise(i) fixed << setprecision(i)
using lint = long;
using llint = long long;
using namespace std;

int main() {
    fastIO;
    int n;
    cin >> n;
    set<char> Arale;
    rep(i, n) {
        char ch;
        cin >> ch;
        Arale.insert(ch);
    }

    if (Arale.size() == 3)
        cout << "Three";
    else
        cout << "Four";
}


Measured memory_bytes: 3612
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,a,b = list(map(int, input().split()))
if a<=b:
    if a!=b and n==1:
        ans = 0
    else:
        ans = (b*(n-1)+a) - (a*(n-1)+b) + 1
else:
    ans = 0
print(ans)

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

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

    int result=0;
    int taps=1;
    while(true){
        if(taps>=B){
            break;
        }else{
            taps+=A-1;
            result+=1;
        }
    }

    cout<<result<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int t;
long long n,m;
long long a[200005],f[200005];
bool cmp(int a,int b)
{
    return a>b;
}
bool check(long long mid)
{
    long long res=m;
        for(int i=1;i<=n;i++)
        {
            if(mid/f[i]<a[i])
            {
                long long x=a[i]-mid/f[i];
                if(x>res)
                    return 0;
                res-=x;
            }
        }
        return 1;
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
        cin>>f[i];
    sort(a+1,a+1+n);
    sort(f+1,f+1+n,cmp);
    long long right=-1;
    for(int i=1;i<=n;i++)
        right= max(right,a[i]*f[i]);
    long long left=0;
    long long ans=0;
    while(left<=right)
    {
        long long mid=(left+right)/2;
        if(check(mid)) right=mid-1,ans=mid;
        else left=mid+1;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3328
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		Obj[] arr = new Obj[n];
		for (int i = 0; i < n; i++) {
			String[] sa = br.readLine().split(" ");
			Obj o = new Obj();
			o.a = Long.parseLong(sa[0]);
			o.b = Long.parseLong(sa[1]);
			arr[i] = o;
		}
		br.close();

		for (Obj o : arr) {
			if (o.a != 0 || o.b != 0) {
				long gcd = gcd(o.a, o.b);
				o.a /= gcd;
				o.b /= gcd;
				if (o.a < 0) {
					o.a *= -1;
					o.b *= -1;
				}
			}
		}

		int zero = 0;
		Map<Obj, Integer> map = new HashMap<>();
		for (Obj o : arr) {
			if (o.a == 0 && o.b == 0) {
				zero++;
			} else {
				addCntMap(map, o);
			}
		}

		int mod = 1000000007;
		long ans = 1;
		Obj[] keys = map.keySet().toArray(new Obj[0]);
		for (Obj k : keys) {
			if (!map.containsKey(k)) {
				continue;
			}
			int v1 = map.get(k);
			long a = power(2, v1, mod);

			Obj k2 = new Obj();
			if (k.b > 0) {
				k2.a = k.b;
				k2.b = -k.a;
			} else if (k.b == 0) {
				k2.b = 1;
			} else {
				k2.a = -k.b;
				k2.b = k.a;
			}
			Integer v2 = map.get(k2);
			if (v2 != null) {
				long a2 = power(2, v2, mod) - 1;
				a += a2;
				map.remove(k2);
			}
			ans *= a;
			ans %= mod;
		}
		ans--;
		ans += zero + mod;
		ans %= mod;
		System.out.println(ans);
	}

	static long power(long x, long n, int m) {
		if (n == 0) {
			return 1;
		}
		long val = power(x, n / 2, m);
		val = val * val % m;
		if (n % 2 == 1) {
			val = val * x % m;
		}
		return val;
	}

	static void addCntMap(Map<Obj, Integer> map, Obj key) {
		if (map.containsKey(key)) {
			map.put(key, map.get(key) + 1);
		} else {
			map.put(key, 1);
		}
	}

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

	static class Obj {
		long a, b;

		@Override
		public boolean equals(Object o) {
			Obj o2 = (Obj) o;
			if (a == o2.a && b == o2.b) {
				return true;
			}
			return false;
		}

		@Override
		public int hashCode() {
			return (int) (a * b);
		}
	}
}


Measured memory_bytes: 66712
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
#include <set>
#include <map>
using namespace std;

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

	int a, b;
	cin >> a >> b;
	int x = b - a;
	int y = x * (x + 1) / 2;
	cout << y - b << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
int main(){
  int n,count; cin>>n; count=0;
  int a[n];
  rep(i,n) cin>>a[i];
  
  rep(i,n){
    if(a[i]==count+1){
      count++;
    }
  }
  if(count==0) cout<<-1<<endl;
  else cout<<n-count<<endl;
}


Measured memory_bytes: 1152
#include<cstdio>
using namespace std;

const int N_MAX = 100005;

int main(){
  int point[N_MAX];
  int N, K, Q;
  scanf("%d %d %d", &N, &K, &Q);

  for(int i= 0; i < N; i++) point[i] = 0;

  for(int i = 0; i < Q; i++){
    int A;
    scanf("%d", &A);
    point[A-1]++;
  }

  for(int i = 0; i < N; i++){
    if (point[i] > Q - K) printf("Yes\n");
    else printf("No\n");
  }

  return 0;
}

Measured memory_bytes: 1024
#include<cstdio>
int main()
{
	int a, b=0, c;
	scanf("%d", &a);
	c=a;
	while(c>0)
	{
		b+=c%10;
		c/=10;
	}
	a%b?printf("No\n"):printf("Yes\n");
	return 0;
}

Measured memory_bytes: 256
#include<cstdio>

int main()
{
	int n,i,s=0,x,t=-1;scanf("%d",&n);
	for(i=0;i<n;i++)scanf("%d",&x),s+=x,(t==-1||x<t)&&x%10&&(t=x);
	printf("%d\n",s%10?s:t==-1?0:s-t);
}

Measured memory_bytes: 128
N=input()
a=input().split()
N=int(N)
for i in range(N):
    a[i]=int(a[i])

#処理
a=sorted(a,reverse=True)

score_a=0
score_b=0

for i in range(N):
    if i%2==0:
        score_a+=a[i]
    else:
        score_b+=a[i]

print(score_a-score_b)

Measured memory_bytes: 3064
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>
#include <stack>
#include <assert.h>
#include <unordered_set>
#include <random>



using namespace std;
using ll = long long;
using ull = unsigned long long;

const ll INF = 1e16;
const ll MOD = 1e9 + 7;

#define REP(i, n) for(ll i = 0; i < n; i++)













int h, w;
char s[2000][2001];
int y_c[2000][2000], x_c[2000][2000];
int yy, xx;
 
int dfs1(int y, int x, int cnt){
    yy = max(yy, y);
    if(y >= h || s[y][x] == '#') return cnt;
    return y_c[y][x] = dfs1(y + 1, x, cnt + 1);
}
 
int dfs2(int y, int x, int cnt){
    xx = max(xx, x);
    if(x >= w || s[y][x] == '#') return cnt;
    return x_c[y][x] = dfs2(y, x + 1, cnt + 1);
}
 
 
int main(){
    scanf("%d %d", &h, &w);
    for(int i = 0; i < h; i++){
        scanf("%s", s[i]);
    }
    for(int j = 0; j < w; j++){
        yy = 0;
        int i = 0;
        while(i < h){
            dfs1(i, j, 0);
            i = yy + 1;
        }
    }
    for(int i = 0; i < h; i++){
        xx = 0;
        int j = 0;
        while(j < w){
            dfs2(i, j, 0);
            j = xx + 1;
        }
    }
    int ans = 0;
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            ans = max(ans, y_c[i][j] + x_c[i][j] - 1);
        }
    }
    printf("%d\n", ans);
}

Measured memory_bytes: 35456
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7;

char a[10][10];

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n;
    cin >> n;
    vector<int> v(n);
    for(int i = 0; i < n; i++) cin >> v[i];
    sort(v.rbegin(), v.rend());
    priority_queue< int > pq;
    ll ans = v[0];
    pq.push(v[1]);
    pq.push(v[1]);
    for(int i = 2; i < n; i++){
        auto p = pq.top();
        pq.pop();
        ans += p;
        pq.push(v[i]);
        pq.push(v[i]);
    }
    cout << ans;


    return 0;
}


Measured memory_bytes: 5056
A, B = map(int, input().split())
S = input()
isOK = True
for i in range(len(S)):
  if i == A:
    if S[i] != "-":
      isOK = False
      break
  else:
    if S[i] == "-":
      isOK = False
      break
print("Yes" if isOK else "No")

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

int main(){
    int n,tot;
    cin >> n >> tot;
    int x=-1, y=-1, z=-1;
    for(int i=n; i>=0; i--){
        for(int j=n-i; j>=0; j--){
            if((10000*i + 5000*j + 1000*(n-i-j) ) == tot){
                x=i;
                y=j;
                z=n-i-j;
                break;
            }
        }
        if(x != -1){
            break;
        }
    }
    cout << x << " " << y << " " << z << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#include<set>
#include<tuple>
#include<ctime>
#include<functional>
#include<cmath>
#include<cassert>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> p; 
#define rep(i,n) for(ll i=0;i<(n);i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define br() p("")
#define pn(s) cout << (#s) << " " << (s) << endl
#define p_yes() p("Yes")
#define p_no() p("No")
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))

int main(){
    string s,t;
    cin>>s>>t;
    int flag=0;
    rep(i,s.size()){
        
            if(s[i]!=t[i]) flag=1;
        
    }
    if(flag) p("No");
    else p("Yes");
}

Measured memory_bytes: 3624
#include<stdio.h>

static const int N = 1000;

void trace(int A[], int n){
  int i;
  for ( i = 1; i <= n; i++ ){
    if ( i > 1 ) printf(" ");
    printf("%d", A[i]);
  }
  printf("\n");
}

int main(){
  int n, i, j,v;
  int A[N+1];
  scanf("%d", &n);

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

  for(i=1;i<=n;i++){
    v = A[i];
    j = i - 1;


    while(j >= 0 && A[j] > v){
      A[j+1] = A[j];
      j--;
    }
      A[j+1] = v;
       trace(A, n);
  }
	

  return 0;
}

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

typedef long long ll;

const int N = 1e5 + 5;

int n, ara[N];

int main()
{
#ifdef TooLazy
    freopen("in.txt", "r", stdin);
#endif // TooLazy

    cin >> n;
    for(int i=1; i<=n; i++) {
        cin >> ara[i];
    }
    int cnt = 0;
    for(int i=1; i<=n; i++) {
        if( ara[i] == i ) {
            swap(ara[i], ara[i+1]);
            cnt++;
        }
    }

    cout << cnt << "\n";

    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
#include <set>
#include <cstdio>
using namespace std;
using ll = long long;


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


int main() {

	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	cout << (!n) << endl;
}

Measured memory_bytes: 3648
/*#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <array>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <string>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
*/

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define FOR(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define SORT(c) sort((c).begin(),(c).end())

typedef long long ll;
const ll INF = LLONG_MAX - 100;
const ll mod = 2e9 + 7;
const int MAX_N = 5e5 + 5;
int dx[] = { -1LL,0,1LL,0 }, dy[] = { 0,1LL,0,-1LL };
vector<ll> prime;

ll inv[MAX_N], fac[MAX_N];

template <class T = ll> T in() { T x; cin >> x; return (x); }
inline ll GCD(ll a, ll b) { ll c; while (b != 0) { c = a % b; a = b; b = c; }return a; }
inline ll LCM(ll a, ll b) { return a * b / GCD(a, b); }
inline ll POW(ll a, ll b) { ll c = 1LL; while (b > 0) { if (b & 1LL) { c = a * c%mod; }a = a * a%mod; b >>= 1LL; }return c; }
inline void _nCr() { fac[0] = 1LL; for (int i = 1LL; i < MAX_N; i++) { fac[i] = fac[i - 1LL] * i%mod; }for (int i = 0; i < MAX_N; i++) { inv[i] = POW(fac[i], mod - 2); } }
inline ll nCr(ll n, ll r) { return (fac[n] * inv[r] % mod)*inv[n - r] % mod; }
inline void PRI(ll n) { bool a[n + 1LL]; for (int i = 0; i < n + 1LL; i++) { a[i] = 1LL; }for (int i = 2; i < n + 1LL; i++) { if (a[i]) { prime.pb(i); ll b = i; while (b <= n) { a[b] = 0; b += i; } } } }

signed main() {
	int H,W,h,w;
	cin >> H >> W >> h >> w;
	int ans[H][W];
	int sum = 0;
	REP (i,H) {
		REP (j,W) {
			if (i % h == h - 1 && j % w == w - 1) {
				ans[i][j] = -(h * w - 1) * 1000 - 1;
			}
			else ans[i][j] = 1000;
			sum += ans[i][j];
		}
	}
	if (sum <= 0) {
		cout << "No" << endl;
	} else {
		cout << "Yes" << endl;
		REP (i,H) {
			REP (j,W) {
				cout << ans[i][j] << " ";
			}
			cout << endl;
		}
	}
}

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

#define fi first
#define se second
#define be begin
#define en end
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define ALL(a) (a).be() , (a).en()
#define REP(i,n) for(int i=0;i<(n);i++)        //repeat n times
#define REP2(i,s,n) for(int i=(s);i<(n);i++)   //repeat from s to n 
#define REPD(i,n) for(int i=(n);i>=0;i--)      //repeat from n to 0
#define REPD2(i,s,e) for(int i=(s);i>=(e);i--) //repeat from s to e
#define RANGE(i,v) for(auto &i:v)                  //repeat range
#define ASIZE(a) (sizeof(a) / sizeof(a[0]))          //array size

using LL = long long;

template<typename T1,typename T2> using P = pair< T1, T2 >;
using Pii = P<int,int>;
using Pll = P<LL,LL>;
using Pdd = P<double,double>;
using Psi = P<string,double>;

template<typename T> using V = vector< T >;
using Vi = V<int>;
using Vll = V<LL>;
using Vs = V<string>;

template<typename T1,typename T2> using M = map< T1, T2>;
using Mii = M<int, int>;
using Msi = M<string, int>;

const int MOD = 1000000007;
const int INF = 1999999999;
const LL INFLL = 999999999999999LL;
const double EPS = 1e-10;

struct edge{
    int src; int dst; int weight;
    edge() : src(0), dst(0), weight(0) {}
    edge(int s, int d, int w) : src(s), dst(d), weight(w) {}
};

using edges = V<edge>;
using graph = V<edges>;

void add_edge(edges &g,int s, int d, int w=1, bool undirected = true){
    g.pb(edge(s,d,w));
    if(undirected) g.pb(edge(d,s,w));
}
void add_edge(graph &g,int s, int d, int w=1, bool undirected = true){
    g[s].pb(edge(s,d,w));
    if(undirected) g[d].pb(edge(d,s,w));
}

P<Vi,Vi> dijkstra(graph &g, int s){
    int n=g.size(); int visit[n]; Vi dist(n);
    Vi dir(n,-1);
    priority_queue<P<int,Pii>,V<P<int,Pii>>,greater<P<int,Pii>>> q;
    REP(i,n){visit[i]=0; dist[i]=INF/2;}
    dist[s]=0;
    q.push(mp(0,mp(s,-1)));
    while(!q.empty()){
        Pii tk;
        int d,t,k; 
        tie(d,tk)=q.top();
        tie(t,k) = tk;
        q.pop();
        if(visit[t]==1){continue;}
        visit[t]=1; dist[t]=d; dir[t] = k;
        for(auto &e:g[t]){
            if(dist[e.dst]<=d+e.weight){continue;}
            q.push(mp(d+e.weight,mp(e.dst,t)));
        }
    }
    return {dist,dir};
}

int main(){
    int N,M;
    cin>>N>>M;
    graph G(N);
    REP(i,M){
        int a,b;
        cin>>a>>b;
        a--; b--;
        add_edge(G,a,b);
    }

    auto [dist,dir] = dijkstra(G,0);

    cout<<"Yes"<<endl;
    REP(i,N-1){
        cout<<dir[i+1]+1<<endl;
    }
    return 0;
}

Measured memory_bytes: 16252
fun main(args: Array<String>) {
    codefestival2016qualb_b()
}

fun codefestival2016qualb_b() {
    val (n, a, b) = readLine()!!.split(' ').map { it.toInt() }
    val s = readLine()!!

    var countRemain = a + b
    var foreignRemain = b

    val answer = s.map {
        when (it) {
            'a' -> {
                if (countRemain > 0) {
                    countRemain--
                    "Yes"
                } else "No"
            }
            'b' -> {
                if (countRemain > 0 && foreignRemain > 0) {
                    countRemain--
                    foreignRemain--
                    "Yes"
                } else "No"
            }
            else -> "No"
        }
    }.joinToString(System.lineSeparator())

    println(answer)
}


Measured memory_bytes: 43552
#include<iostream>
#include<string>
#include<algorithm>
#define REP(i, n) for(int i = 0; i < n; ++i)
using namespace std;

int main()
{
    string s;
    cin >> s;
    int l = s.length();
    string t = "";
    REP(i,l){
        if (i % 2 == 0){
            t += s[i];
        }
    }
    cout << t << endl;
    return 0;
}

Measured memory_bytes: 576
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include<random>
#include<math.h>
#include<limits.h>
#include<iterator>
#include<queue>
#include<functional>
#define rep(i,a) for(int i=0;i<a;i++)
#define nrep(i,a,b) for(int i=a;i<b;i++)
#define mrep(i,a) for(int i=a;i>=0;i--)
#define ll long long
#define vl vector<ll> 
#define vvl vector<vector<ll> > 
#define vb vector<bool> 
#define vvb vector<vector<bool> > 
#define INF 11234567890123456789
using namespace std;

int main(){
	ll x, a, b; cin >> x >> a >> b;
	cout << (abs(x - a) < abs(x - b) ? "A" : "B") << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int a[]={0,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 n;
	scanf("%d",&n);
	printf("%d\n",a[n]);
	
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,A,B,ans[300005];
int main()
{
	scanf("%d%d%d",&n,&A,&B);
	if(A+B>n+1||A==0||B==0) {printf("-1\n");return 0;}
	if(B==1)
	{
		if(A!=n) {printf("-1\n");return 0;}
		for(int i=1;i<n;++i) printf("%d ",i);
		printf("%d\n",n);
		return 0;
	}
	if(A==1)
	{
		if(B!=n) {printf("-1\n");return 0;}
		for(int i=1;i<n;++i) printf("%d ",n-i+1);
		printf("%d\n",1);
		return 0;
	}
	int J=n,L,R;
	for(int i=A;i>=1;--i) ans[i]=J,J--;
	L=B,R=n-A,J=B-1;
	for(int i=A+1;i<=A+B-1;++i) ans[i]=J,J--;
	
	A--,B--;
	int l=1,r=n;
	while(l<r)
	{
		int mid=(l+r)>>1;
		int s=(R-L+1)/mid;
		if((R-L+1)%mid!=0) s++;
		if(s<=B) r=mid;
		else l=mid+1;
	}
	if(l>A) {printf("-1\n");return 0;}
	J=A+B+2;
	while(R-L+1>=A)
	{
		int k=R-l+1;
		for(int i=J;i<=J+l-1;++i) ans[i]=k++;
		J=J+l,R-=l;
	}
	for(int i=J;i<=n;++i) ans[i]=L++;
	for(int i=1;i<n;++i) printf("%d ",ans[i]);
	printf("%d\n",ans[n]);
	return 0;
}

Measured memory_bytes: 3328
#include <cstdio>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>

#define a first
#define b second
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR (i, 0, n)
#define _ << " _ " <<
#define TRACE(x) cerr << #x << " = " << x << endl
#define debug(...) fprintf(stderr, __VA_ARGS__)
//#define debug
//#define TRACE(x)

using namespace std;
using pii = pair<int, int>;
					     
typedef long long llint;

const int MAXN = 2010;
const int MOD = 924844033;

inline int add(int a, int b) { return (a + b) % MOD; }
inline int mul(int a, int b) { return int((llint)a * b % MOD); }

int n, k, m, sol;
vector<int> v;
int dp[2*MAXN][MAXN], cnt[2*MAXN][MAXN];

int f[MAXN][MAXN], fact[2*MAXN];

void recalc() {
  f[0][0] = 1;
  FOR(rem, 1, MAXN) FOR(t, 0, rem+1) {
    int ret = 0;
    ret = add(ret, f[rem-1][t]);
    ret = add(ret, f[max(0, rem-2)][t-1]);
    f[rem][t] = ret;
  }
}

int g(int i, int rem) {
  if (i == (int)v.size()) return (rem == 0) ? 1 : 0;
  if (dp[i][rem] != -1) return dp[i][rem];

  int ret = 0;
  
  for (int j = 0; j <= min(rem, v[i]); ++j)
    ret = add(ret, mul(f[v[i]][j], g(i+1, rem-j)));

  return dp[i][rem] = ret;
}

int main(void) {
  fact[0] = 1;
  FOR(i, 1, MAXN)
    fact[i] = mul(fact[i-1], i);
  
  memset(dp, -1, sizeof(dp));
  scanf("%d %d",&n,&k);
  REP(i, min(n,k)) {
    int tot = 0;
    for (int j = i; j < n; j += k)
      ++tot;
    v.push_back(tot-1);
    v.push_back(tot-1);
  }

  recalc();

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

  REP(t, n+1) {
    int tmp = g(0, t);
    tmp = mul(tmp, fact[n-t]);
    if (t % 2 == 1) tmp = mul(tmp, -1);
    sol = add(sol, tmp);
  }

  if (sol < 0) sol += MOD;

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

  return 0;
}


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

int main()
{
    int n;
    cin>>n;
    int f=0,ans=0;
    string s="ABC";
    for(int i=0;i<n;i++)
    {
        char ch;
        cin>>ch;
        if(ch==s[f])
            f++;
        else 
        {
            f=0;
            if(ch==s[f])
                f++;
        }
        if(f==3)
        {
            ans++;
            f=0;
            // cout<<i<<" ";
        }
    }
    cout<<ans;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<stack>
#include<vector>
#define INFTY 500000
#define WHITE 0
#define GRAY 1
#define BLACK 2
using namespace std;

int color[120],d[120];
vector<pair<int,int> > v[120];
int n;

void start(int x){
  d[x]=0;
  while(true){
    int minimumd=INFTY,u;
    for(int i=0;i<n;i++){
      if(color[i]!=BLACK && minimumd>d[i]){
        minimumd=d[i];
        u=i;
      }
    }
    if(minimumd==INFTY) break;
    color[u]=BLACK;
    for(int i=0;i<v[u].size();i++){
      int temp=v[u][i].first;
      if(d[temp]>d[u]+v[u][i].second && color[temp]!=BLACK){
        d[temp]=d[u]+v[u][i].second;
        color[temp]=GRAY;
      }
    }
  }
  for(int i=0;i<n;i++){
    cout<<i<<" "<<d[i]<<endl;
  }
}

int main(){
  int u,k,v1,c;
  cin>>n;
  for(int i=0;i<n;i++){
    d[i]=INFTY;
  }
  for(int i=0;i<n;i++){
    cin>>u>>k;
    for(int j=0;j<k;j++){
      cin>>v1>>c;
      v[u].push_back(make_pair(v1,c)); 
    }
  }
  start(0);
}



Measured memory_bytes: 3136
#include<bits/stdc++.h>
using namespace std;
long N,memo[111][6][6][6][6],mod=1e9+7;
// b3は3文字前,b2は2文字前,b1は1文字前
long rec(int now,int b3,int b2,int b1,int b){
  // printf("%d %d %d %d %d\n",now,b3,b2,b1,b);
  if(memo[now][b3][b2][b1][b]!=-1)return memo[now][b3][b2][b1][b];
  if(b3==0&&b2==1&&b==2)return 0;// AG?Cの場合
  if(b3==0&&b1==1&&b==2)return 0;// A?CGの場合
  if(b2==0&&b1==1&&b==2)return 0;// ?AGCの場合
  if(b2==0&&b1==2&&b==1)return 0;// ?ACGの場合
  if(b2==1&&b1==0&&b==2)return 0;// ?GACの場合
  if(now==N)return 1;
  long ans=0;
  for(int i=0;i<4;i++)ans+=rec(now+1,b2,b1,b,i);
  return memo[now][b3][b2][b1][b]=ans%mod;
}
int main(){
  cin>>N;
  memset(memo,-1,sizeof(memo));
  cout<<rec(0,4,4,4,4)<<endl;
}


Measured memory_bytes: 1408