akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <complex>
#include <utility>
#include <vector>
#include <string>
#include <queue>
#include <tuple>
#include <cmath>
#include <bitset>
#include <cctype>
#include <set>
#include <map>
#include <numeric>
#include <functional>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
using namespace std;
using ll = long long;
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; }
inline void Yes(bool condition){ if(condition) PRINT("Yes"); else PRINT("No"); }
template<class itr> void cins(itr first,itr last){
    for (auto i = first;i != last;i++){
        cin >> (*i);
    }
}
template<class itr> void array_output(itr start,itr goal){
    string ans = "",k = " ";
    for (auto i = start;i != goal;i++) ans += to_string(*i)+k;
    if (!ans.empty()) ans.pop_back();
    PRINT(ans);
}
ll gcd(ll a, ll b) {
    return a ? gcd(b%a,a) : b;
}
const ll INF = 1e9;
const ll MOD = 1000000007;
typedef pair<ll,ll> P;
const ll MAX = 20000;
constexpr ll nx[4] = {1,0,-1,0};
constexpr ll ny[4] = {0,1,0,-1};
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,b;
    cin >> n;
    vector<ll> a(n);
    ll sum = 0,odd = 0,even = 0;
    rep(i,n){
        cin >> b;
        sum += b;
        a[i] = b;
        if (i%2 == 1) even += a[i];
    }
    sum /= 2;
    vector<ll> ans(n);
    sum -= even;
    ans[0] = sum;
    rep(i,1,n){
        ans[i] = a[i-1]-ans[i-1];
    }
    rep(i,n) ans[i] *= 2;
    array_output(all(ans));
}


Measured memory_bytes: 4096
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
typedef long long ll;
// #include<C:\Users\J\Desktop\AC\athead.h>
#define showa(v) for(int iii = 0; iii < v.size(); iii++){ cout << v[iii] << " ";} cout << endl;
#define show(iiii) cout << iiii << endl; 
#define shows(iiiii) cout << iiiii << " ";
#include<iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include <cmath>
#include <cstdlib>
#include <cassert>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#include<tuple>
#include <utility>
#include <map>
using namespace std;
 
int main(){
    int n;
    string s;
    cin >> n >> s;
    if(n%2 == 0){
        rep(i,n/2){
            if(s[i] != s[i+(n/2)]){
                cout << "No";
                return 0;
            }
        }
        cout << "Yes" << endl;
    }
    else{
        cout << "No";
        return 0;
    }

}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <cmath>
#include <string>
#include <bitset>
#include <functional>
#include <set>
#include <map>
#include <array>
#include <numeric>

using namespace std;
typedef long long int ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define fst first
#define snd second
#define pb push_back
#define ALL(obj) (obj).begin(), (obj).end()
#define debug(x) cout << #x << ": " << x << endl
//#define int long long int
const int MOD = 1000000007;
const int INF = 1001001000;
const double EPS = 0.000000001;

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

bool pairCompare(const P& pair1, const P& pair2) {
    return pair1.second > pair2.second;
}

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n, a, b, c, d;
  string s;
  cin >> n >> a >> b >> c >> d;
  cin >> s;
  bool ans = true;
  if(c < d){
    bool flag = false;
    for(int i = a; i < c; i++){
      if(s[i] == '#'){
        if(flag) {
          ans = false;
          break;
        }
        else flag = true;
      }
      else flag = false;
    }
    flag = false;
    for(int i = b; i < d; i++){
      if(s[i] == '#'){
        if(flag) {
          ans = false;
          break;
        }
        else flag = true;
      }
      else flag = false;
    }
  }
  else if(c > d){
    bool flag = false;
    int flag2 = 0;
    bool ansflag = false;
    for(int i = b-1; i < d+1; i++){
      if(s[i] == '#'){
        flag2 = 0;
        if(flag) {
          ans = false;
          break;
        }
        else flag = true;
      }
      else if(s[i] == '.'){
        flag = false;
        if(flag2 >= 2){
          ansflag = true;
        }
        else flag2++;
      }
    }
    if((a + 1 == b) && d == b){
      s[b-1] = '#';
      ansflag = true;
    }
    if(s[b-2] == '.' && s[b] == '.') ansflag = true;
    if(!ansflag) ans = false;
    flag = false;
    for(int i = a; i < c; i++){
      if(s[i] == '#'){
        if(flag) {
          ans = false;
          break;
        }
        else flag = true;
      }
      else flag = false;
    }

  }
  else ans = false;
  if(ans) cout << "Yes" << endl;
  else cout << "No" << endl;

  return 0;
}


Measured memory_bytes: 592
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n); i++)
#define rep1(i,n) for(int i = 1; i <= (n); i++)
#define all(v) v.begin(),v.end()
#define vi vector<int>
#define vi2 vector<vector<int>>
#define vl vector<long long>
#define vl2 vector<vector<long long>>

template <class T> T maxAny(T a, T b){
    if(a > b) return a;
    else return b;
}

template <class T> T minAny(T a, T b){
    if(a > b) return b;
    else return a;
}

int main(){
    char c;
    cin >> c;
    c += 1;
    cout << c << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long   ll;
typedef unsigned long long   ull;
typedef long double ld;
typedef pair<ll, ll>    pll;
typedef pair<ull, ull>    pull;
typedef pair<ll, ll>  pii;
typedef pair<ld, ld>  pld;
typedef long double ld;
ll mod = 1e9+7;
ll x, y;
ll fact(ll x){
    ll ret = 1;
    for(ll i = 1; i <= x; ++i)
        ret = ret*i%mod;
    return ret;
}
ll inv(ll x){
    ll ret = 1;
    ll y = mod-2;
    while(y > 0){
        if(y%2)
            ret = ret*x%mod;
        y /= 2;
        x = x*x%mod;
    }
    return ret;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> x >> y;
    ll a, b;
    if((2*y-x) % 3 != 0){
        cout << 0;
        return 0;
    }
    a = (2*y-x)/3;
    b = y-2*a;
    if(a < 0 || b < 0){
        cout << 0;
        return 0;
    }
    cout << fact((a+b))*inv(fact(a))%mod*inv(fact(b))%mod << "\n";
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define MOD(x) ((x)%mod)
#define pii pair<int,int>
#define mp(a,b) make_pair(a,b)
#define root 1
using namespace std;
int n;
long long mod;
struct edge
{
	int to,next;
}e[200005];
int cnt;
int head[100005];
void ins(int u,int v)
{
	cnt++;
	e[cnt].to=v;
	e[cnt].next=head[u];
	head[u]=cnt;
}
long long low[100005];
long long up[100005];
long long ans[100005];
vector<long long>son[100005];
long long pre[100005],suf[100005];
long long ksm(long long a,long long x)
{
	long long base=1;
	while(x)
	{
		if(x&1) base=MOD(base*a);
		a=MOD(a*a);
		x>>=1;
	}
	return base;
}
void dfs1(int u,int fa)
{
	low[u]=1;
	for(int i=head[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(v==fa) continue;
		dfs1(v,u);
		son[u].push_back(v);
		low[u]=MOD(low[u]*(low[v]+1));
	}
	int up=son[u].size();
	for(int i=0;i<up;i++)
	{
		if(i==0) pre[son[u][i]]=1;
		else pre[son[u][i]]=MOD(pre[son[u][i-1]]*(low[son[u][i-1]]+1));
	}
	for(int i=up-1;i>=0;i--)
	{
		if(i==up-1) suf[son[u][i]]=1;
		else suf[son[u][i]]=MOD(suf[son[u][i+1]]*(low[son[u][i+1]]+1));
	}
}
void dfs2(int u,int fa)
{
	up[u]=1;
	if(fa==0) up[u]=1;
	else
	{
		//up[u]=MOD(MOD(up[fa]*low[fa])*ksm(low[u]+1,mod-2)+1);
		up[u]=MOD(MOD(up[fa]*pre[u])*suf[u]+1);
	}
	ans[u]=MOD(low[u]*up[u]);
	for(int i=head[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(v==fa) continue;
		dfs2(v,u);
	}
}
int main()
{
	scanf("%d%lld",&n,&mod);
	for(int i=1;i<n;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		ins(u,v);
		ins(v,u);
	}
	dfs1(1,0);
	dfs2(1,0);
	for(int i=1;i<=n;i++)
		printf("%lld\n",ans[i]);
	return 0;
}



Measured memory_bytes: 17792
#include<stdio.h>
int main(void) {
	long long n, i, sum = 0;

	scanf("%lld", &n);

	for (i = 1; i <= n; i++) {
		if (
			(i % 3 != 0) && (i % 5 != 0)
			)
			sum = sum + i;
	}

	printf("%lld", sum);
	
	return 0;
}

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

using namespace std;

const int max_n = 111, inf = 1000111222;

int n, a[max_n][max_n], sum[max_n];
vector<int> x, y;

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            a[i][j] = 1;
        }
        int sum = n + 1 - n % 2;
        a[i][sum - i] = 0;
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            if (a[i][j]) {
                x.push_back(i);
                y.push_back(j);
                sum[i] += j;
                sum[j] += i;
            }
        }
    }
    printf("%d\n", x.size());
    for (int i = 0; i < x.size(); ++i) {
        printf("%d %d\n", x[i], y[i]);
    }
    return 0;
}


Measured memory_bytes: 384
package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	as := make([]int, n)
	bs := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&as[i], &bs[i])
	}

	c := 0
	for i := n - 1; i >= 0; i-- {
		a, b := as[i], bs[i]
		a += c
		b = ((a + b - 1) / b) * b
		c += b - a
	}
	fmt.Println(c)
}


Measured memory_bytes: 5504
#include <bits/stdc++.h>
using namespace std;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n, s, k;
	cin >> n >> k >> s;
	for (int i = 0; i < k; i++) {
		cout << s << " ";
	}
	n -= k;
	if (n >= s) {
		for (int i = 0; i < n; i++) {
			cout << s + 1 << " ";
		}
	}
	else for (int i = 0; i < n; i++) cout << 1 << " ";
}

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

#define ll long long

int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    int res = 10000000,cnt=0;

    for(int i=0;i<n;i++)
    {
    	if(a[i]<=res)
    	{
    		res = a[i];
    	}
    	if(a[i]==res)
    		cnt++;
    }
    cout<<cnt;
}

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

int nextPlayer(char c){
  if(c == 'a') return 0;
  if(c == 'b') return 1;
  if(c == 'c') return 2;
}

int main(void){
  vector<string> s(3);

  for(int i = 0; i < s.size(); i ++)
    cin >> s.at(i);

  for(int i = 0; i < s.size(); i ++)
    s.at(i) += 'D';

  int i = 0;
  int x = 0, y = 0, z = 0;
  while(1){
    if(i == 0){
      if(s.at(0).at(x) == 'D') break;
      else i = nextPlayer(s.at(0).at(x++));
    }
    if(i == 1){
      if(s.at(1).at(y) == 'D') break;
      else i = nextPlayer(s.at(1).at(y++));
    }
    if(i == 2){
      if(s.at(2).at(z) == 'D') break;
      else i = nextPlayer(s.at(2).at(z++));
    }
  }

  if(i == 0) cout << "A";
  if(i == 1) cout << "B";
  if(i == 2) cout << "C";

  cout << endl;

  return 0;
}
      


Measured memory_bytes: 256
def valid(num,l):
    while(num>0):
        if (num%10) in l:
            return 0
        num = num//10
    return 1

n,k=map(int,input().split(' '))
l = [int(x) for x in input().split(' ')]
for i in range(100000):
    if valid(n+i,l) == 1:
        print(n+i)
        break


Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
   ll n,capacity;cin>>n>>capacity;
   ll w[n+1],v[n+1];
   for(ll i=1;i<=n;i++)
    cin>>w[i]>>v[i];

   ll dp[n+1][capacity+1];
   memset(dp,0,sizeof(dp));

   for(ll i=1;i<=n;i++)
   {
       for(ll j=1;j<=capacity;j++)
       {
           if(j>=w[i])
            dp[i][j]=max((v[i]+dp[i-1][j-w[i]]),dp[i-1][j]);
           else
            dp[i][j]=dp[i-1][j];
       }
   }
   cout<<dp[n][capacity];
}


Measured memory_bytes: 79104
using System;
using System.Collections.Generic;
using System.Text;

namespace test
{
	class MainClass
	{
		public static void Main (string[] args)
		{
			string[] inputArray = Console.ReadLine ().Split (' ');
			int[] numArray = Array.ConvertAll (inputArray, new Converter<string, int> (s => int.Parse (s)));
			Array.Sort (numArray);
			Array.Reverse (numArray);

			int i = 1;
			foreach (int a in numArray) {
				Console.Write (a);
				if (i <= 4) {
					Console.Write (" ");
				} else {
					Console.WriteLine ();
				}
				i++;
			}

		

		}
					
	}
	
}

Measured memory_bytes: 5772
import bisect
a,b,q = map(int, input().split())
s=[int(input()) for i in range(a)]
t=[int(input()) for i in range(b)]
x=[int(input()) for i in range(q)]
s.insert(0, -(10**11))
s.append(10**11)
t.insert(0, -(10**11))
t.append(10**11)

for xi in x:
  sb = bisect.bisect(s, xi)
  tb = bisect.bisect(t, xi)
  
  print(min((abs(s[sb]-xi)+abs(t[tb]-s[sb])), 
              (abs(s[sb]-xi)+abs(t[tb-1]-s[sb])),
              (abs(s[sb-1]-xi)+abs(t[tb]-s[sb-1])),
              (abs(s[sb-1]-xi)+abs(t[tb-1]-s[sb-1])),
              (abs(t[tb]-xi)+abs(s[sb]-t[tb])),
              (abs(t[tb]-xi)+abs(s[sb-1]-t[tb])),
              (abs(t[tb-1]-xi)+abs(s[sb]-t[tb-1])),
              (abs(t[tb-1]-xi)+abs(s[sb-1]-t[tb-1]))))

Measured memory_bytes: 16168
#include <bits/stdc++.h>
using namespace std;
#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()
#define pb push_back
using ll = long long;
using P = pair<int, int>;
using Graph = vector<vector<int>>;

int main(){
    int x; cin >> x;
    if(x >= 2000) cout << 1 << endl;
    else if(x >= 100 && x <= 105 * (x/100)) cout << 1 << endl;
    else cout << 0 << endl;
}

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

  int main() {
    int n, k;
    cin >> n >> k;
    vector<long long> num(k, 0);
    for(int i = 1; i <= n; i++) num[i%k]++;
    long long res = 0;
    for (int a = 0; a < k; ++a) {
      int b = (k - a) % k;
      int c = (k - a) % k;
      if ((b + c) % k == 0)
      res += num[a] * num[b] * num[c];
    }
    cout << res << endl;

    return 0;
  }


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

public class Main {
	static FastReader f = new FastReader();
	static PrintWriter out = new PrintWriter(System.out);
	

	public static void main(String[] args) {
		//int t = f.nextInt();
		//while(t-- > 0)
			solve();
		out.close();
	}

	static void solve() {
		int n = f.nextInt();
		
		long ans = 0;
		for(int i=1;i<=n;i++) {
			long min = 0;
			long max = n;

			while(min < max) {
				long mid = (min + max) / 2;

				if(i * mid < n) {
					min = mid+1;
				} else {
					max = mid-1;
				}
			}

			long loc = Math.max(0, min-3);
			for(long j = Math.max(0, min-3);j<min+3;j++) {
				if(j * i <= n) {
					loc = j;
				} else {
					break;
				}
			}
			if(loc * i == n) {
				loc--;
			}
			ans += loc;
		}

		out.println(ans);
	}

	static class FastReader {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(IOException ioe) {
					ioe.printStackTrace();
				}
			}
			return st.nextToken();
		}

		String nextLine() {
			String s = "";
			try {
				s = br.readLine();
			} catch(IOException ioe) {
				ioe.printStackTrace();
			}

			return s;
		}

		int  nextInt() {
			return Integer.parseInt(next());
		}
	}
}

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

int main()
{
	string s,t,ans;
	cin>>s>>t;
	int dp[5000][5000]={0};
	for(int i=0;i<=s.length();i++)
	{
		for(int j=0;j<=t.length();j++)
		{
			if(i==0||j==0)
				dp[i][j]=0;
			else if(s[i-1]==t[j-1])
				{dp[i][j]=1+dp[i-1][j-1];
				}	
			else
				dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
		}
	}
	int i=s.length();
	int j=t.length();
	while(i>0&&j>0)
	{
		if(s[i-1]==t[j-1])
		{
			ans.push_back(s[i-1]);
			i--;
			j--;
		}
		else if(dp[i-1][j]>dp[i][j-1])
			i--;
		else
			j--;
	}
	reverse(ans.begin(),ans.end());
	if(ans.size()==0)
		cout<<" ";
	else
		cout<<ans;

}

Measured memory_bytes: 97920
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#include <list>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
ll f[10000010];
int main()
{
    int n; cin>>n;
    for(int d=1; d<=n; d++){
        for(int i=d; i<=n; i+=d) f[i]++;
    }
    ll ans=0;
    for(int i=1; i<=n; i++){
        ans+=i*f[i];
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 81796
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<bool> vb;
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define in insert
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int INF = 1e9 + 5;
int main(){
    string s;
    cin >> s;
    for(int i = 0; i < s.size(); i++) if(s[i] == '1') cout << '9';
    else cout << "1";
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){
    int L, R, i, j, mod;
    int imod = 2020;

    0 <= L < 2000000000;
    0 < R <= 2000000000;

    scanf("%d%d", &L, &R);

    if ((R - L) >= 2019){
            printf("0\n");
            return 0;
    }else{
    for(i=L;i<R;i++){
        for(j=i+1;j<=R;++j){
          mod = (i%2019)*(j%2019)%2019;
          if(mod < imod){
           imod = mod;
          }
            }
        }
    } 



    printf("%d\n", imod);
    return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
#define max 100
#define INFTY 1000000000
#define WHITE 0
#define GRAY 1
#define BLACK 2

int n, m[max][max];
int d[max]; //d[]..頂点vへの道で最小の重みを入れる


void dijkstra();

int main(){

  int k, c, u, v;
  int i, j;

  scanf("%d", &n);

  for(i=0; i<n; i++){
    for(j=0; j<n; j++){
      m[i][j] = INFTY;
    }
  }

  for(i=0; i<n; i++){
    scanf("%d %d", &u, &k);
    
    for(j=0; j<k; j++){
      scanf("%d %d", &v, &c);
      m[u][v]=c;
    }
  }

  dijkstra();

  //print
  for(i=0; i<n; i++){
    printf("%d", i);
    if(d[i]!= INFTY) printf(" %d\n", d[i]);
  }
  //for(i=0; i<n; i++) printf("%d %d\n", i, d[i]);
  

  return 0;
}

void dijkstra(){

  int minv, u;
  //int d[max]; //d[]..頂点vへの道で最小の重みを入れる
  int color[max];
  int i, v;

  for(i=0; i<n; i++){//初期化
    d[i]= INFTY;
    color[i]= WHITE;
  }

  d[0]=0;
  color[0]=GRAY;

  while(1){

    minv=INFTY;
    u= -1;

    for(i=0; i<n; i++){
      
      if( d[i]<minv && color[i] != BLACK){
	u=i;
	minv=d[i];
      }
    }
    if(u == -1) break;
    color[u]=BLACK;

    for(v=0; v<n; v++){
      
      if(color[v]!= BLACK && m[u][v] != INFTY){

	if( d[u]+ m[u][v] < d[v]){
	  d[v] = d[u]+m[u][v];
	  color[v]=GRAY;
	}
      }
    }
  }//while終了
}



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


using ll = long long;
using pii = pair<int, int>;
using Vi = vector<int>;

int main() {
  set<string> SET;
  string s;
  int K;
  cin >> s >> K;
  
  for(int i = 0; i<s.size(); i++){
    for(int j = 1; j<=K; j++){
      string t = s.substr(i,j);
      SET.insert(t);
    }
  }
  
  int cnt = 0;
  
  for(auto c : SET){
    cnt++;
    if(cnt==K){
      cout << c << endl;
    }
  }
}      
       





Measured memory_bytes: 4764
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        n: usize,
        k: usize,
        _aa: [usize;n]
    }
    let t = n - k;
    let s = k - 1;
    println!("{}", (t + s - 1) / s + 1);
}


Measured memory_bytes: 6396
#include <iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<stdio.h>

using namespace std;
int main()
{
    int n,flag=1;
    cin>>n;
    int a[120]= {0};
    for(int i=1; i<=n; i++)
        cin>>a[i];
    for(int i=1; i<=n; i++)
    {
        if((a[i]%2==0)&&(a[i]%3!=0&&a[i]%5!=0))
        {
            flag=2;
            break;
        }
    }
    if(flag==2)
        cout<<"DENIED";
    else
        cout<<"APPROVED";
}




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

void BubbleSort(int a[],int n){
    for(int i=0;i<n;i++){
        int minj=i;
        bool flag=false;
        for(int j=i;j<n;j++){
            if(a[i]>a[j]){
                minj=j;
                flag=true;
            }
        }
        if(flag)swap(a[i],a[minj]);
    }

//    for(int x=0;x<n;x++)cout<<a[x]<<" ";
//    cout<<endl;
}

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

    BubbleSort(line,n);

    int sum=0;  for(int i=0;i<n-1;i++)sum+=line[i];

    if(line[n-1]<sum)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;

    return 0;
}


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

int main(){
    lo n;
    cin >> n;
    lo arr[n+1];
    map<lo,lo> m;
    
    for(lo i = 1;i <= n;i++) {
        cin >> arr[i];
        m[arr[i]]++;
    }
    vector<pair<lo,lo> > v;
    lo sum = 0;
    for(map<lo,lo> :: iterator it = m.begin(); it!=m.end();it++){
        sum += ((*it).second * ((*it).second-1)/2);
    }
    for(lo i = 1;i <= n;i++){
        
        lo res = (m[arr[i]] * (m[arr[i]]-1)/2) - ((m[arr[i]]-1) * (m[arr[i]] - 2)/2);
        cout << sum - res << endl;
        
        
    }
     
}

Measured memory_bytes: 11008
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<unordered_map>
using namespace std;
long long dp[100][100][5000];
 
int main(){
	int N, A;
	cin>>N>>A;
	vector<int> x(N);
	int X = 0;
	for(int i = 0; i < N; i++){
		cin>>x[i];
		X = max(X, x[i]);
	}
	X = max(A, X);
	dp[0][0][0] = 1;
	for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++){
			for(int k = 0; k <= 5000; k++){
				if (dp[i][j][k] == 0)continue;
				dp[i + 1][j+1][k + x[i]] += dp[i][j][k];
				dp[i + 1][j][k] += dp[i][j][k];
				
			}
		}
	}
	long long ans = 0;
	for(int i = 1; i <= N; i++){
		ans += dp[N][i][i * A];
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 151808
#include<bits/stdc++.h>
using namespace std;
int n,k,ans=1;
int main()
{
    cin>>n>>k;
    for(int i=0;i<n;i++)
    {
        if(ans>k) ans+=k;
        else ans*=2;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
# 入力
N,M,X=map(int,input().split())
l=list(map(int,input().split()))

# 現在位置
_X=X

# コスト
c1=c2=0

# 目的地に向かって1ずつ動かす（X->N）
for i in range(N-X):
  # 移動
  _X+=1

  # 料金所があればコストを加算
  if l.count(_X)>0:
    c1+=1

# 現在位置をリセット
_X=X

# 目的地に向かって1ずつ動かす（X->0）
for i in range(X-0):
  # 移動
  _X-=1

  # 料金所があればコストを加算
  if l.count(_X)>0:
    c2+=1

# コストが小さい方を出力
print(min(c1,c2))

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
#define rep(i,x) for(ll i = 0; i < (ll)(x); i++)
#define pb push_back
#define eb emplace_back
#define debug(x) cerr << #x << ": " << (x) << "\n";
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> Pll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<vector<vector<ll>>> vvvl;
const ll INF = numeric_limits<ll>::max()/4;
const ll MOD = 1e9+7;
const int n_max = 1e5+10;

void print() {
    cout << endl;
}

template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
    cout << head;
    if (sizeof...(tail) != 0) cout << ' ';
    print(forward<Tail>(tail)...);
}

template <class T>
void print(vector<T> &vec) {
    for (auto& a : vec) {
        cout << a;
        if (&a != &vec.back()) cout << ' ';
    }
    cout << endl;
}

template <class T>
void print(vector<vector<T>> &df) {
    for (auto& vec : df) {
        print(vec);
    }
}


int main(){
    ll n,k; cin >> n >> k;
    vector<ll> a(n);
    rep(i,n) cin >> a[i];
    vector<ll> ind(2*1e5+20,-1), next(n);
    rep(i,2){
        for(int j = n-1; 0 <= j; j--){
            if(ind[a[j]] != -1) next[j] = ind[a[j]];
            ind[a[j]] = j;
        }
    }
    vector<ll> bs(n,-1);
    ll pos = 0, cnt = 0, pre_cnt = 0;
    while(bs[pos] == -1 ) {
        bs[pos] = cnt;
        if(next[pos] > pos)cnt += next[pos] + 1 - pos ;
        else cnt += next[pos] + 1 + n - pos;
        if(n * k <= cnt)break;
        pos = next[pos] + 1;
        if(pos == n)pos = 0;
    }

    // print(next);
    // print(bs);
    // debug(cnt);debug(pos);
    vector<ll> ans;
    if(cnt < n*k){
        ll t = n*k - 1 - bs[pos];
        t %= (cnt - bs[pos]);
        // t += bs[pos];
        cnt = n*k-1 - t;
        while(true){
            bs[pos] = cnt;
            if(next[pos] > pos)cnt += next[pos] + 1 - pos ;
            else cnt += next[pos] + 1 + n - pos;
            if(n * k <= cnt)break;
            pos = next[pos] + 1;
            if(pos == n)pos = 0;
        }
        // cnt = t;
        // debug(cnt);
    }

    cnt = bs[pos];
    // debug(cnt);debug(pos);
    // pos++;
    // if(pos == n)pos = 0;
    bitset<200010> b(0);
    for(ll i = cnt; i < n*k; i++){
        if(b[a[pos]] == 0){
            ans.emplace_back(a[pos]);
            b[a[pos]] = 1;
        }
        else{
            while(b[a[pos]] == 1){
                ll t = ans.back();ans.pop_back();
                b[t] = 0;
            }
        }
        pos++;
        if(pos == n)pos = 0;
    }

    for(auto i : ans)cout << i << " ";
    cout << endl;

}

Measured memory_bytes: 9456
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <cassert>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
#include <unordered_set>
//#pragma GCC optimize("Ofast")  //デバッグ時にoptimized-outされて邪魔だった
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define irep(it, stl) for(auto it = stl.begin(); it != stl.end(); it++)
#define drep(i,n) for(int i = (n) - 1; i >= 0; --i)
#define fin(ans) cout << (ans) << '\n'
#define mp(p,q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define floatprec(dig) fixed << setprecision(dig)
#define Sort(a) sort(a.begin(), a.end())
#define Rort(a) sort(a.rbegin(), a.rend())
#define MATHPI acos(-1)
#define itn int;
#define invar(typ, var) typ var; cin >> var;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
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;}
struct io{io(){ios::sync_with_stdio(false);cin.tie(0);}};
const int INF = INT_MAX;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;
const double EPS = 1e-9;

signed main(void) {
  cin.tie(0); ios::sync_with_stdio(false);
  
  invar(long double, a);
  invar(long double, b);
  invar(long double, c);
  
  long double eps = 1.0E-14;
  if(sqrt(a) + sqrt(b) + eps < sqrt(c)) {
    fin("Yes");
  } else {
    fin("No");
  }
  
}

Measured memory_bytes: 256
#pragma region template
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vld = vector<ld>;
using vvld = vector<vld>;
using vvvld = vector<vvld>;
using vs = vector<string>;
using pll = pair<ll, ll>;
using vp = vector<pll>;
template <typename T>
using pqrev = priority_queue<T, vector<T>, greater<T>>;
#define rep(i, n) for (ll i = 0, i##_end = (n); i < i##_end; i++)
#define repb(i, n) for (ll i = (n)-1; i >= 0; i--)
#define repr(i, a, b) for (ll i = (a), i##_end = (b); i < i##_end; i++)
#define reprb(i, a, b) for (ll i = (b)-1, i##_end = (a); i >= i##_end; i--)
#define ALL(a) (a).begin(), (a).end()
#define SZ(x) ((ll)(x).size())
//*
constexpr ll MOD = 1e9 + 7;
/*/
constexpr ll MOD = 998244353;
//*/
constexpr ll INF = 1e+18;
constexpr ld EPS = 1e-12L;
constexpr ld PI = 3.14159265358979323846L;
constexpr ll GCD(ll a, ll b) { return b ? GCD(b, a % b) : a; }
constexpr ll LCM(ll a, ll b) { return a / GCD(a, b) * b; }
template <typename S, typename T>
inline bool chmax(S &a, const T &b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <typename S, typename T>
inline bool chmin(S &a, const T &b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
#ifdef OJ_LOCAL
#include "dump.hpp"
#else
#define dump(...) ((void)0)
#endif
template <typename T>
bool print_(const T &a) {
  cout << a;
  return true;
}
template <typename T>
bool print_(const vector<T> &vec) {
  for (auto &a : vec) {
    cout << a;
    if (&a != &vec.back()) {
      cout << " ";
    }
  }
  return false;
}
template <typename T>
bool print_(const vector<vector<T>> &vv) {
  for (auto &v : vv) {
    for (auto &a : v) {
      cout << a;
      if (&a != &v.back()) {
        cout << " ";
      }
    }
    if (&v != &vv.back()) {
      cout << "\n";
    }
  }
  return false;
}
void print() { cout << "\n"; }
template <typename Head, typename... Tail>
void print(Head &&head, Tail &&... tail) {
  bool f = print_(head);
  if (sizeof...(tail) != 0) {
    cout << (f ? " " : "\n");
  }
  print(forward<Tail>(tail)...);
}
#pragma endregion

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(20);
  ll n, d;
  cin >> n >> d;
  ll ans = 0;
  rep(i, n){
    ll x, y;
    cin >> x >> y;
    ans += (x*x+y*y<=d*d);
  }
  print(ans);
}


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

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define INF (1<<29)
#define EPS (1e-8)

string name[10];
int w[10], s[10];
int num[10], an[10];
double mi;
int n;

void dfs(int pos, double sum, double g) {
	if (pos == n) {
		g /= (double)sum;
		if (mi > g + EPS) {
			mi = g;
			REP(i, 10) an[i] = num[i];
		}
	}
	else {
		REP(i, n) if (num[i] == -1 && s[i] >= sum - EPS) {
			num[i] = pos;
			dfs(pos + 1, sum + w[i], g + w[i] * (n - pos));
			num[i] = -1;
		}
	}
}

int main() {
	while (cin >> n, n) {
		REP(i, n) cin >> name[i] >> w[i] >> s[i];

		fill(num, num + n, -1);
		fill(an, an + n, -1);
		mi = INF;

		dfs(0, 0.0, 0.0);
		vector<int> ans(n);
		for (int i = n - 1; i >= 0; i--) REP(j, n) if (an[j] == i) ans[n - i - 1] = j;
		REP(i, n) cout << name[ans[i]] << endl;
	}
	return 0;
}

Measured memory_bytes: 1200
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using p = pair<int,int>;
int main() {
  	int K;
  	cin >> K;
  	int S[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};
  	if (K == 1) {
    	cout << "1" << endl;
  	}
  	else {
    	int ans = K - 1;
    	cout << S[ans] << endl;
  	}
  	return 0;	
}

Measured memory_bytes: 256
from collections import defaultdict
N = int(input())
D = list(map(int, input().split()))
D_dict = defaultdict(int)
for d in D:
    D_dict[d] += 1
M = int(input())
T = list(map(int, input().split()))
T_dict = defaultdict(int)
for t in T:
    T_dict[t] += 1

for target, t_cnt in T_dict.items():
    d_cnt = D_dict[target]
    if t_cnt > d_cnt:
        print('NO')
        exit()
print('YES')

Measured memory_bytes: 57344
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int x = sc.nextInt();
		int[] a = new int[m];
		for (int i = 0; i < m; i++) {
			a[i] = sc.nextInt();
		}
		// xから左側のコストを計算
		int lec = 0;
		for (int i = 1; i < x; i++) {
			for (int j = 0; j < m; j++) {
				if (i == a[j]) {
					lec++;
				}
			}
		}
		// xから右側のコストを計算
		int ric = 0;
		for (int i = x + 1; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (i == a[j]) {
					ric++;
				}
			}
		}
		System.out.println(Math.min(lec, ric));
	}

}


Measured memory_bytes: 23124
import java.util.Scanner;

public class Main {

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

		long N = scan.nextLong();
		long M = scan.nextLong();
		long rest = 0;
		
		if(M > 2*N){
			rest = M - 2 * N;
			long quo = rest / 4;
			System.out.println(N + quo);
		}else{
			long c = M /2;
			System.out.println(c);
		}
		
	}

}


Measured memory_bytes: 23636
class Card:
    def __init__(self, card):
        self.value = int(card[1])
        self.card = card


def selectionSort(A, N):
    for i in range(N):
        minj = i
        for j in range(i, N):
            if A[j].value < A[minj].value:
                minj = j
        if minj != i:
            tmp = A[i]
            A[i] = A[minj]
            A[minj] = tmp

    return A


def bubbleSort(A, N):
    flag = 1
    while flag:
        flag = 0
        for j in range(N-1, 0, -1):
            if A[j].value < A[j-1].value:
                tmp = A[j]
                A[j] = A[j-1]
                A[j-1] = tmp
                flag = 1

    return A


def check_stable(A, cards):
    for num in range(1, 10):
        As = []
        Cs = []
        for a in A:
            if a.value == num:
                As.append(a.card)
        for c in cards:
            if c.value == num:
                Cs.append(c.card)

        if As != Cs:
            print("Not stable")
            return
    else:
        print("Stable")
        return


def main():
    N = int(input())
    cards = [Card(i) for i in input().split()]
    bubble_cards = bubbleSort(cards.copy(), N)
    selection_cards = selectionSort(cards.copy(), N)

    print(*[bc.card for bc in bubble_cards])
    check_stable(bubble_cards, cards)
    print(*[sc.card for sc in selection_cards])
    check_stable(selection_cards, cards)


if __name__ == "__main__":
    main()


Measured memory_bytes: 5620
#include<stdio.h>
#define A 2000

int n,a[A];

int makeCombination(int i,int x){
  int r;
  if(x==0) return 1;
  if(i>=n) return 0;
  r = makeCombination(i+1,x) || makeCombination(i+1,x-a[i]);
  return r;
      }

int main(){
  
  int q,i,m;

  scanf("%d",&n);

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

  scanf("%d",&q);

  for(i=0;i<q;i++){
    scanf("%d",&m);
    if(makeCombination(0,m)==1) printf("yes\n");
    else printf("no\n");
  }

  return 0;
}



Measured memory_bytes: 2044
n = int(input())
a = list(map(int, input().split()))
dic = {}
for i in range(n):
  if a[i] in dic:
    dic[a[i]] += 1
  else:
    dic[a[i]] = 1
clear = 0
for k, v in dic.items():
  if k > v:
    clear += v
  else:
    clear += v-k
print(clear)


Measured memory_bytes: 21792
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> T;

int N;
string s;

int main(void){
    
    scanf("%d", &N);
    cin >> s;
    
    int ans = 0;
    for(int i = 1; i < N; ++i){
        map<char, int> a, b;
        for(int j = 0; j < i; ++j) ++a[s[j]]; 
        for(int j = i; j < N; ++j) ++b[s[j]];
        int cnt = 0;
        for(auto m : a) if(b.find(m.first) != b.end()) ++cnt;
        ans = max(ans, cnt);
     }
     printf("%d\n", ans);
    
    return 0;
}


Measured memory_bytes: 384
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<utility>
#include<cmath>
#include<functional>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
void sort(int &a,int &b)
{
	if(a>b)
		swap(a,b);
}
void open(const char *s)
{
#ifndef ONLINE_JUDGE
	char str[100];
	sprintf(str,"%s.in",s);
	freopen(str,"r",stdin);
	sprintf(str,"%s.out",s);
	freopen(str,"w",stdout);
#endif
}
int rd()
{
	int s=0,c;
	while((c=getchar())<'0'||c>'9');
	do
	{
		s=s*10+c-'0';
	}
	while((c=getchar())>='0'&&c<='9');
	return s;
}
int upmin(int &a,int b)
{
	if(b<a)
	{
		a=b;
		return 1;
	}
	return 0;
}
int upmax(int &a,int b)
{
	if(b>a)
	{
		a=b;
		return 1;
	}
	return 0;
}
int v[200010];
int f[1<<21];
int g[1<<21];
int l[30][200010];
int r[30][200020];
int a[200010];
int b[200010];
int main()
{
//	open("agc012e");
	int n;
	scanf("%d%d",&n,&v[1]);
	int i,j;
	for(i=1;i<=n;i++)
		scanf("%d",&a[i]);
	int t=1;
	while(1)
	{
		v[t+1]=v[t]/2;
		t++;
		if(!v[t])
			break;
	}
	for(i=1;i<=t;i++)
	{
		for(j=1;j<=n;j++)
			if(j==1||a[j]-a[j-1]>v[i])
				l[i][j]=j;
			else
				l[i][j]=l[i][j-1];
		for(j=n;j>=1;j--)
			if(j==n||a[j+1]-a[j]>v[i])
				r[i][j]=j;
			else
				r[i][j]=r[i][j+1];
	}
	memset(f,0,sizeof f);
	int all=1<<t;
	for(i=0;i<all;i++)
		for(j=1;j<=t;j++)
			if(!((i>>(j-1))&1))
			{
				if(f[i]==n)
					upmax(f[i|(1<<(j-1))],f[i]);
				else
					upmax(f[i|(1<<(j-1))],r[j][f[i]+1]);
			}
	for(i=0;i<all;i++)
		g[i]=n+1;
	for(i=0;i<all;i++)
		for(j=1;j<=t;j++)
			if(!((i>>(j-1))&1))
			{
				if(g[i]==1)
					upmin(g[i|(1<<(j-1))],g[i]);
				else
					upmin(g[i|(1<<(j-1))],l[j][g[i]-1]);
			}
	if(f[all-2]>=n)
	{
		for(i=1;i<=n;i++)
			printf("Possible\n");
		return 0;
	}
	for(i=0;i<all;i++)
		if(!(i&1)&&(r[1][f[i]+1]>=n||g[(all-1)^i^1]<=r[1][f[i]+1]+1))
			b[l[1][f[i]+1]]=1;
	int last=0;
	for(i=1;i<=n;i++)
	{
		if(b[i])
			last=i;
		if(l[1][i]<=last||(i<=r[1][1]&&r[1][1]>=g[all-2]-1))
			printf("Possible\n");
		else
			printf("Impossible\n");
	}
	return 0;
}

Measured memory_bytes: 50176
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;

ll b[1<<16];
ll dp[1<<16];
int main (){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    ll a[n][n];
    for(int i =0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            cin >> a[i][j];
    ll ALL = (1<<n) - 1;
    for(ll mask = 0; mask <= ALL; mask++) {
        b[mask] = 0;
        for(int i = 0; i < n; ++i) {
            if(1<<i & mask) {
                for(int j = i+1; j < n; ++j)
                    if(1<<j & mask)
                        b[mask] += a[i][j];
            }
        }
    }
    ;
    for(ll mask = 0; mask <= ALL; mask++) {
        dp[mask] = max(0ll, b[mask]);
        for(ll sub = mask; sub > 0; sub = (sub-1) & mask) {
            dp[mask] = max(dp[mask], dp[sub] + dp[mask ^ sub]);
        }
    }
    cout << dp[ALL];
    return 0;
}


Measured memory_bytes: 1280
#include <stdio.h>
 
int main(void) {
  int s = 0;
  char c;
 
  while ((c = getchar()) != EOF) {
    if (c >= '0' && c <= '9') {
      s += c - '0';
      continue;
    }

    if (s == 0) {
      break;
    }

    printf("%d\n", s);
    s = 0;
  }
 
  return 0;
}

Measured memory_bytes: 524
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;

bool is_palindrome(string s) {
    bool res = true;
    for(lint i=0; i<s.length(); i++) {
        res &= (s[i] == s[s.length()-i-1]);
    }
    return res;
}

int main() {
    string s;
    cin >> s;

    lint n = s.length();

    bool ans = true;
    ans &= is_palindrome(s);
    ans &= is_palindrome(s.substr(0, (n-1)/2));
    ans &= is_palindrome(s.substr((n+3)/2-1));

    cout << (ans ? "Yes" : "No") << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)  for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
#define pb push_back
#define eb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define ub(v,k) (upper_bound(all(v),k)-v.begin())
#define fi first
#define se second
#define pi M_PI
#define PQ(T) priority_queue<T>
#define SPQ(T) priority_queue<T,vector<T>,greater<T>>
#define dame(a) {out(a);return 0;}
#define decimal cout<<fixed<<setprecision(15);
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef tuple<ll,ll,ll,ll> PPP;
typedef multiset<ll> S;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;
using vp=vector<P>;
using vvp=vector<vp>;
using vb=vector<bool>;
using vvb=vector<vb>;
const ll inf=1001001001001001001;
const int INF=1001001001;
const int mod=998244353;
const double eps=1e-10;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
template<class T> void outvvp(T v){rep(i,v.size())outvp(v[i]);}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
template<class T> bool isin(T x,T l,T r){return (l)<=(x)&&(x)<=(r);}
template<class T> void yesno(T b){if(b)out("yes");else out("no");}
template<class T> void YesNo(T b){if(b)out("Yes");else out("No");}
template<class T> void YESNO(T b){if(b)out("YES");else out("NO");}
template<class T> void noyes(T b){if(b)out("no");else out("yes");}
template<class T> void NoYes(T b){if(b)out("No");else out("Yes");}
template<class T> void NOYES(T b){if(b)out("NO");else out("YES");}
void outs(ll a,ll b){if(a>=inf-100)out(b);else out(a);}
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll modpow(ll a,ll b){a%=mod;if(b==0)return 1;if(b&1)return a*modpow(a,b-1)%mod;ll k=modpow(a,b/2);return k*k%mod;}
vi color;
vvi g;
P res;
bool is_nibu=true;
void dfs(int i,int c){
    if(!is_nibu)return;
    if(color[i]==c)return;
    if(color[i]!=-1){
        is_nibu=false;
        return;
    }
    if(c)res.fi++;
    else res.se++;
    color[i]=c;
    for(auto x:g[i])if(color[x]!=1-c)dfs(x,1-c);
}
int main(){
    ll n,m;cin>>n>>m;
    vvb v(n,vb(n,true));
    g=vvi(n);
    rep(i,m){
        ll a,b;cin>>a>>b;a--;b--;
        if(a<b)swap(a,b);
        v[a][b]=false;
    }
    rep(i,n)rep(j,i)if(v[i][j]){
        g[i].pb(j);
        g[j].pb(i);
    }
    color=vi(n,-1);
    vp d;
    rep(i,n)if(color[i]==-1){
        res=P(0,0);
        dfs(i,0);
        if(res.fi>res.se)swap(res.fi,res.se);
        d.eb(res);
    }
    if(!is_nibu)dame(-1);
    bitset<360> dp;
    dp.set(0);
    for(auto x:d)dp=(dp<<x.fi)|(dp<<x.se);
    for(int i=n/2;i>=0;i--)if(dp.test(i))dame(n*(n-1)/2-i*(n-i));
}

Measured memory_bytes: 6016
#include <bits/stdc++.h>
using namespace std;
int main(){
	int n;
	int a[100000];
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
		if(a[i]%2){
			cout<<"first"<<endl;
			return 0;
		}
	}
	cout<<"second"<<endl;
	return 0;
}

Measured memory_bytes: 640
import math
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse = True)
half = math.floor(N/2)
ans = 2**(half)
if N%2 == 1 and A[-1] !=0:
  ans = 0
for i in range(half):
  if A[2*i] == N-2*i-1 and A[2*i+1] == N-2*i-1:
    continue
  else:
    ans = 0
    break
print(ans%(10**9+7))

Measured memory_bytes: 13812
#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <functional>
#include <algorithm>
#include <climits>
#include <cmath>
#include <iomanip>
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    string T; cin >> T;
    rep(i, T.length()) {
        if(T[i] == '?') T[i] ='D';
    }
    cout << T << endl;

    return 0;
}


Measured memory_bytes: 3772
#include <bits/stdc++.h>
using namespace std;
 
double a[500000];
 
int main() {
         int n;
         double mean;
          int ans;
         while(true) {
                 cin >> n;
                 if (n == 0) break;
 
                 for(int i = 0;i < n;i++) cin >> a[i];
 
                 mean = 0;
                 ans = 0;
 
                 for(int i = 0;i < n;i++) mean += a[i];
 
                 mean /= n;
 
                 for(int i = 0;i < n;i++) {
                         if (a[i] <= mean) ans += 1;
                 }
 
                 cout << ans<< "\n";
         }
 }


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

long long acum[200005];
long long m = 10e8 + 7;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  long long n,k;
  cin >> n >> k;
  for (long long i = 1; i <= n; i++) acum[i] = acum[i - 1] + i;
  long long ans = 0;
  for (int i = k - 1; i <= n; i++) {
    long long min = acum[i];
    long long max = acum[n] - acum[n - (i + 1)];
    long long total = max - min + 1;
    ans = ((total % m) + (ans % m)) % m;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 5120
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n, i=0;
    char s[100000];
    string rot;
    rot="ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ";
    cin >> n >> s;
    while(s[i]!='\0'){
        s[i]=rot[s[i]-'A'+n];
        i++;
    }
    cout << s <<endl;

    return 0;
}

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

using namespace std;


int main(void){

  int LEN;
  cin >> LEN;
  
  vector<int > Imigrant;
  for (int i = 0; i < LEN; i++)
  {
    int A; cin >> A;
    Imigrant.push_back(A);
  }
  

  for (vector<int >::iterator itr = Imigrant.begin(); itr != Imigrant.end(); itr++)
  {
    if( *itr % 2 == 0 ){
     if( (*itr % 3 == 0)){
       continue;
     }else if( *itr % 5 == 0){
       continue;
     }else {
      cout << "DENIED" << endl;
      return 0;
     }
    }
  }
  
  
  cout << "APPROVED" << endl;

  return 0;
}




Measured memory_bytes: 888
N = int(input())
p = [int(x) for x in input().split()]
a = [0]*N
a[0] = p[0]
for i in range(1,N):
    a[i] = min(a[i-1],p[i])
ans = 0
for i in range(N):
    if a[i] >= p[i]:
        ans += 1
print(ans)

Measured memory_bytes: 25768