akhauriyash/Code-Regression huggingface dataset:
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int V = Integer.parseInt(sc.next());
        int E = Integer.parseInt(sc.next());
        long[][] edge = new long[V][V];
        long INF = 200_000_000_000_000L;
        for (int i=0;i<V;i++) {
            for (int j=0;j<V;j++) {
                if (i==j) {
                    continue;
                }
                edge[i][j] = INF;
            }
        }
        for (int i=0;i<E;i++) {
            int s = Integer.parseInt(sc.next());
            int t = Integer.parseInt(sc.next());
            long d = Long.parseLong(sc.next());
            edge[s][t] = d;
        }
        for (int k=0;k<V;k++) {
            for (int i=0;i<V;i++) {
                for (int j=0;j<V;j++) {
                    if(edge[i][k] != INF && edge[k][j] != INF) {
                    if (edge[i][j]>edge[i][k]+edge[k][j]) {
                        edge[i][j] = edge[i][k]+edge[k][j];
                    }
                    }
                }
            }
        }
        int flag = 0;
        for (int i=0;i<V;i++) {
            if (edge[i][i]!=0) {
                System.out.println("NEGATIVE CYCLE");
                flag=1;
                break;
            }
        }
        if (flag==0) {
            for (int i=0;i<V;i++) {
                for (int j=0;j<V;j++) {
                    if (edge[i][j]==200_000_000_000_000L) {
                        System.out.print("INF");
                    } else {
                        System.out.print(edge[i][j]);
                    }
                    if (j==V-1) {
                        System.out.println("");
                    } else {
                        System.out.print(" ");
                    }
                }
            }
        }
        // System.out.println(Arrays.deepToString(edge));
    }
}


Measured memory_bytes: 48420
#include<bits/stdc++.h>
using namespace std;
int mi(int a,int b,int c)
{
    int x=a>b?b:a;
    return x>c?c:x;
}
int main()
{
    int n,k;
    cin>>n>>k;
    int a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    int dp[n];
    dp[0]=0;
    for(int i=1;i<n;i++)
        dp[i]=INT_MAX;
    if(k!=1)
    {


    for(int i=1;i<n;i++)
    {
        if(i<k)
        {
            for(int j=1;j<k;j++)
            {
                if(i-j-1>=0)
                {
                    dp[i]=mi(dp[i-j]+abs(a[i]-a[i-j]),dp[i-j-1]+abs(a[i]-a[i-j-1]),dp[i]);
                }
                else if(i-j>=0)
                {
                    dp[i]=dp[i-j]+abs(a[i]-a[i-j]);
                }
            }
        }
        else
        {
            for(int j=1;j<k;j++)
            {
                dp[i]=mi(dp[i-j]+abs(a[i]-a[i-j]),dp[i-j-1]+abs(a[i]-a[i-j-1]),dp[i]);
            }
        }
    }
    }
    else
    {
        for(int i=1;i<n;i++)
            dp[i]=dp[i-1]+abs(a[i]-a[i-1]);
    }
   // for(int i=0;i<n;i++)
     //  cout<<dp[i]<<endl;
   cout<<dp[n-1];
}


Measured memory_bytes: 1024
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <string>

using namespace std;

int main() {

	while (1) {
		int N;
		cin >> N;
		int cnt = N;
		if (N==0) break;
		int x[20], y[20];
		bool flag[20] = { false };
		for (int i = 0; i < N; i++) {
			cin >> x[i] >> y[i];
			flag[i] = true;
		}
		int M, posx=10, posy=10;
		cin >> M;
		for (int i = 0; i < M; i++) {
			char d;
			int dis;
			cin >> d >> dis;
			for (int j = 0; j < dis; j++) {
				if (d == 'N') posy++;
				if (d == 'E') posx++;
				if (d == 'S') posy--;
				if (d == 'W') posx--;
			//	cout << "x : " << posx << " y : " << posy << endl;
				for (int k = 0; k < N; k++) {
					if (x[k] == posx && y[k] == posy && flag[k]) {
						cnt--;
						flag[k] = false;
					}
				}
			}
		
		}
		if (cnt == 0) cout << "Yes" << endl;
		else cout << "No" << endl;
	}

	return 0;
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define endl "\n"
#define pb push_back
#define f(i,n) for(i=0;i<n;i++)
#define F(i,a,b) for(i=a;a<=b;i++)
#define arr(a,n) for( i=0;i<n;i++)cin>>a[i];
#define fi first
#define se second
#define mp make_pair
#define mod 1000000007
#define YES cout<<"YES"<<endl;
#define Yes cout<<"Yes"<<endl;
#define NO cout<<"NO"<<endl;
#define No cout<<"No"<<endl;
#define yes cout<<"yes"<<endl;
#define no cout<<"no"<<endl;
#define vi vector<ll>
#define ed end()
#define bg begin()
#define sz size()
#define ln length()
#define s() sort(a,a+n);
#define sr() sort(a,a+n,greater<ll>());
#define v()  sort(v.begin(),v.end());
#define vr() sort(v.begin(),v.end(),greater<ll>());
#define mod 1000000007
#define fast() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
ll gcd(ll a, ll b){if(!b)return a;return gcd(b, a % b);}
ll power(ll x,ll y,ll p){ll res=1;x%=p;while(y>0){if(y&1)res=(res*x)%p;y=y>>1;x=(x*x)%p;}return res;}
int main() {
    /*#ifndef ONLINE_JUDGE
        // for getting input from input.txt
        freopen("input.txt", "r", stdin);
        // for writing output to output.txt
        freopen("output.txt", "w", stdout);
    #endif*/
        /* 
        Ofcourse it's Hard.
        It's supposed to be Hard.
        If it's easy everyone would do it.
        HARD IS WHAT MAKES IT GREAT

        YESTERDAY U SAID TOMORROW

        SLOWLY BECOMING THE PERSON I 
        SHOULD HAVE BEEN A LONG TIME AGO

        SAME TASK CAN'T BE FOUND DIFFICULT TWICE

        BTBHWSITW

        SPRH TU KAB P

        CP IS ALL ABOUT THINKING 
        YOU HAVE MUCH MORE POTENTIAL THAN U THINK

        AJIT SHIDDAT 10

        UR DAILY ROUTINE 


        */

fast();
//ll t;cin>>t;while(t--)
{
   string s;
   cin>>s;
   ll n=s.length();
   
   sort(s.begin(),s.end());
   int a[26];
   memset(a,0,sizeof(a));
   for(int i=0;i<n;i++)
    {
      a[s[i]-'a']++;
    } 
    ll idx=-1;
    for(int i=0;i<26;i++)
    {
      if(a[i]==0)
      {
        idx=i;
        break;
      }
    }
    if(idx==-1)
      cout<<"None"<<endl;
    else
      cout<<(char('a'+idx))<<endl;
}
return 0;
}

Measured memory_bytes: 512
#include<iostream>
#include<algorithm>
#include<math.h>
#include<string>
#include<vector>
#include<queue>
#include<deque>
using namespace std;
typedef pair<int, int>P;
typedef pair<int, pair < int, int > > PP;
typedef long long ll;
ll inf = -1;
ll mod = pow(10, 9) + 7;

int main() {
	int n;cin>>n;
	int m1=0,m4=0;
	for(int i=0;i<n;i++){
		int a;cin>>a;
		if(a%4==0){
			m4++;
		}
		else if(a%2!=0){
			m1++;
		}
	}
	if(m1<=m4){
		cout<<"Yes"<<endl;
	}else{
		if(m1==m4+1&&m1+m4==n){
			cout<<"Yes"<<endl;
		}else{
		cout<<"No"<<endl;
		}
	}
	return 0;
}

Measured memory_bytes: 256
from math import ceil


# 川の字に分割
def river(x, y):
    diff = ceil(x / 3) - x // 3
    return diff * y


# T字に分割
def t(x, y):
    def f(uy):
        dy = y - uy
        lx = x // 2
        rx = x - lx
        us = x * uy
        ls = lx * dy
        rs = rx * dy
        return max(us, ls, rs) - min(us, ls, rs)

    return min(f(y // 3), f(ceil(y / 3)))


def solve(h, w):
    return min(river(h, w), river(w, h), t(h, w), t(w, h))


def main():
    h, w = map(int, input().split())

    ans = solve(h, w)
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define pll pair<ll,ll>
#define all(v) v.begin(),v.end()
#define mod 1000000007
#define mx 1000002
mt19937 myrand(time(0));

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(),cout.tie();
    string s,t;
    cin>>s>>t;
    ll ans=0;
    for(int i=0;i<(int)s.size();i++){
        if(s[i]!=t[i]) ans++;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 3872
from functools import reduce
n=int(input())
s=[int(x) for x in list(str(n))]
for i in range(0,len(s)):
    if s[i]==1:
        s[i]=9
    else:
        s[i]=1
print(int(reduce(lambda x, y: x + y, [str(x) for x in s])))

Measured memory_bytes: 3572
#include <bits/stdc++.h>
using namespace std;
 
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
 
using ll = long long;
using P = pair<int,int>;
using graph = vector<vector<int>>;
 
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const ll INF = 1LL<<60;
const ll mod = 1000000007LL;
 
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
 
int main(){
    int N;
    cin>>N;
    vector<ll> v(N);
    rep(i,N) {
        cin>>v[i];
        v[i]*=-1;
    }
    vector<ll> s;
    rep(i,N){
        auto ite = upper_bound(s.begin(),s.end(),v[i]);
        if(ite==s.end()) s.push_back(v[i]);
        else{
            *ite=v[i];
        }
    }
    cout<<s.size()<<endl;
}

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

int main() {
  int n;
  cin >> n;
  
  vector<int> rb(n);
  for(int i=0; i<n; i++) cin >> rb[i];
  
  int cnt = 0;
  for(int i=0; i<n; i++) if(rb[rb[i]-1]==i+1) cnt++;
  
  cout << cnt/2 << endl;
  return 0;
}

Measured memory_bytes: 3708
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
	    // write your code here
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        long[] list = new long[n];

        for (int i = 0; i < n; i++) {
            list[i] = sc.nextLong();
        }

        int start = n - 1;
        StringBuilder builder = new StringBuilder();

        boolean isDown = true;

        for (int i = 0; i < n; i++) {
            builder.append(list[start]);
            if (i != n - 1) {
                builder.append(" ");
            }
            if (start == 1 && isDown) {
                start = 0;
                isDown = false;
                continue;
            }
            if (start == 0 && isDown) {
                start = 1;
                isDown = false;
                continue;
            }
            if (isDown) {
                start -= 2;
            } else {
                start += 2;
            }
        }

        System.out.println(builder);
    }
}

Measured memory_bytes: 92156
n, k = map(int, input().split())
r, s, p = map(int, input().split())
t = input()

point = {"r":p, "s":r, "p":s}

log = ["" for _ in range(k)] 
ans = 0
for i, play in enumerate(t):
    if play == log[i % k]:
        log[i % k] = ""
        continue
    log[i % k] = play
    ans += point[play]
print(ans)

Measured memory_bytes: 3956
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<climits>
#include<iostream>
#include<sstream>
#include<utility>
#include<map>
#include<vector>
#include<queue>
#include<algorithm>
#include<set>
#include<stack>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

bool ch(int a,int b,int c,int x)
{
	return abs(a-b)<=x&&abs(b-c)<=x;
}

int main()
{
	int a,b,c,d;
	scanf("%d%d%d%d",&a,&b,&c,&d);
	if(ch(a,b,c,d)||ch(b,a,c,d)||ch(c,b,a,d)||ch(a,a,c,d))
		puts("Yes");
	else
		puts("No");
}


Measured memory_bytes: 256
program prob3
    implicit none
    integer(8) A, B, C, AA, BB, ans
    read(*,*) A, B, C

    ans = 0
    if(A == B .and. B == C .and. mod(A,2) == 0)then
        write(*,*) -1
        stop
    else
        do while(mod(A,2) == 0 .and. mod(B,2) == 0 .and. mod(C,2) == 0)
            AA = B/2 + C/2
            BB = A/2 + C/2
            C = A/2 + B/2
            A = AA
            B = BB
            ans = ans + 1
        end do

        write(*,*) ans
        stop
     end if

end program prob3

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

bool flag[105];
int main() {
    // freopen("homework.in", "r", stdin);
    // freopen("homework.out", "w", stdout);
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= k; i++) {
        int m;
        cin >> m;
        for (int j = 1; j <= m; j++) {
            int t;
            cin >> t;
            flag[t] = true;
        }
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (!flag[i]) {
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 3628
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <sstream>
#include <iomanip>
#include <queue>
#include <utility>

#define rep(i,n) for(int i = 0; i < n; i++)
#define rep1(i,n) for(int i = 1; i <= n; i++)
#define co(x) cout << x <<endl
#define cs(x) cout << x <<" "
typedef long long ll;

using namespace std;

int main()
{
	int N, M;
	cin >> N >> M;
	vector<pair<ll,ll>> AB(N);
	rep(i, N)
	{
		ll A, B;
		cin >> A >> B;
		AB[i].first = A;
		AB[i].second = B;
	}
	sort(AB.begin(), AB.end());

	int m = 0;
	ll ans = 0;
	rep(i, N)
	{
		if (m+AB[i].second < M)
		{
			m += AB[i].second;
			ans += AB[i].first * AB[i].second;
		}
		else
		{
			ans += AB[i].first *(M - m);
			break;
		}
	}
	co(ans);
	return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define mx 1005
using namespace std;

int main(){
	int ans = 0, k, s;
	scanf("%d%d", &k, &s);
	for(int i = 0; i <= k; i++){
		int t = s - i;
		if(0 <= t && t <= 2*k){
			ans += min(t, 2*k - t) + 1;
		}
	}
	printf("%d\n", ans);
}

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

int main(){
  int n;
  cin >> n;
  
  int *p;
  p = new int[n]; 
  for(int i=0; i<n; i++){
    cin >> p[i];
  }
  
  int ct=0;
  int p1, p2, p3;
  p1 = p[0];
  p2 = p[1];
  for(int i=1; i<n-1; i++){
    p3 = p[i+1];
//    cout << p1 << p2 << p3 << endl;
    if((p1<p2 && p2<=p3)||(p3<p2 && p2<=p1)) ct++;
    p1 = p2;
    p2 = p3;
  }
  
  cout << ct << endl;
  return 0;
}

Measured memory_bytes: 256
from itertools import combinations
N, D = map(int, input().split())
X = []
for _ in range(N):
  X += list(map(int, input().split()))
cnt = 0
for i, j in combinations(range(N),2):
  d = 0
  for k in range(D):
    d += (X[i*D + k] - X[j*D + k])**2
  if int(d**0.5)**2 == d: cnt += 1
print(cnt)

Measured memory_bytes: 38384
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

n = int(input())
m = 0

for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            m += gcd(i,j,k)
print(m)


Measured memory_bytes: 69636
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9 + 5;

int main() {
  int n;
  cin >> n;
  vector<int> sample(n), first(n), second(n);
  for (int i = 0; i < n; i++) {
    cin >> first[i];
  }
  for (int i = 0; i < n; i++) {
    cin >> second[i];
  }

  for (int i = 0; i < n; i++) {
    sample[i] = i + 1;
  }

  int f, s;
  int cnt = 0;
  do {
    for (int i = 0; i < n; i++) {
      if (equal(sample.begin(), sample.end(), first.begin(), first.end())) {
        f = cnt + 1;
      }
      if (equal(sample.begin(), sample.end(), second.begin(), second.end())) {
        s = cnt + 1;
      }
    }
    cnt++;
  } while (next_permutation(sample.begin(), sample.end()));
  cout << abs(s - f) << endl;
  return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <unordered_map>
#include <vector>

using namespace std;

typedef long long lint;

int main() {
  string s;
  cin >> s;
  int i = 0, j = s.size() - 1;
  int result = 0;
  while (j - i + 1 >= 2) {
    if (s[i] == s[j]) {
      ++i, --j;
    } else if (s[i] == 'x') {
      ++i;
      ++result;
    } else if (s[j] == 'x') {
      --j;
      ++result;
    } else {
      result = -1;
      break;
    }
  }
  printf("%d\n", result);
  return 0;
}


Measured memory_bytes: 512
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a = sc.nextInt();
        int b = sc.nextInt();
        
        int sum = 0;
        for(int i = 1;i <= n;i++){
            int tmp = i,dig = 0;
            while(tmp > 0){
                dig += (tmp%10);
                tmp /= 10;
            }
            if(dig >= a && dig <= b)sum += i;
        }
        System.out.println(sum);
    }
}

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

#define ll long long int

ll max(ll a, ll b){
  if(a > b) return a;
  return b;
}

ll min(ll a, ll b){
  if(a < b) return a;
  return b;
}

ll Solve(int N, int R, int S, ll* H, ll* Kai){
  //cout << "Solve: " << R << " " << S << endl;
  ll ret = LLONG_MAX>>2;
  if(R <= 0){
    ret = 0;
  }else if(S == 1){
    ret = H[R];
  }else if(Kai[(N+1)*R+S] >= 0){
    //cout << "sanshou"<< endl;
    ret = Kai[(N+1)*R+S];
  }else{
    for(int i = S-1; i < R; ++i){
      ll tmp = Solve(N, i, S-1, H, Kai) + max(0, H[R] - H[i]);
      //cout << "tmp " << i << " " << (S-1) << " " << tmp << " " << ret << endl;
      ret = min(ret, tmp);
      //cout << "tmp " << i << " " << (S-1) << " " << tmp << " " << ret << endl;
    }
    Kai[(N+1)*R+S] = ret;
  }
  //cout << R << " " << S << " " << ret << endl;
  return ret;
}

int main(){
  int N, K;
  cin >> N >> K;
  ll H[N+1];
  H[0] = 0;
  for(int i = 0; i < N; ++i) cin >> H[i+1];
  ll Kai[(N+1)*(N+1)];
  for(int i = 0; i < (N+1)*(N+1); ++i) Kai[i] = -1;

  //cout << N << " " << K << endl;
  //for(int i = 0; i < N+1; ++i) cout << " " << H[i];
  //cout << endl;
  ll ret = LLONG_MAX >> 2;
  for(int i = N-K; i <= N; ++i){
    ll tmp = Solve(N, i, N-K, H, Kai);
    ret = min(ret, tmp);
  }
  cout << ret << endl;

  return 0;
}


Measured memory_bytes: 1024
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#include<iomanip>
#include<set>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define brep(index,num) for(int index=num-1;index>=0;index--)
#define brep1(index,num) for(int index=num;index>0;index--)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-7
#define mp(a1,a2) make_pair(a1,a2)
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
typedef long long ll;
typedef long double ld;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
int main(){
	int X;
	scan(X);
	int simo=X%100;
	int ue=X/100;
	int need=simo/5+(simo%5!=0);
	if(need<=ue){
		prin(1);
	}
	else prin(0);
	return 0;
}


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

int main() {
	ll n, m, x;
	cin >> n >> m >> x;
	vector<ll> c(n);
	vector<vector<ll>> a(n, vector<ll>(m));
	for (ll i = 0; i < n; ++i) {
		cin >> c[i];
		for (ll j = 0; j < m; ++j)cin >> a[i][j];
	}
	ll ans = 1e15;
	for (ll bit = 0; bit < (1 << n); ++bit) {
		ll price = 0;
		vector<ll> understand(m, 0);
		for (ll i = 0; i < n; ++i) {
			if (bit & (1 << i)) {
				price += c[i];
				for (ll j = 0; j < m; ++j) {
					understand[j] += a[i][j];
				}
			}
		}
		if ((*min_element(understand.begin(), understand.end())) >= x) {
			ans = min(ans, price);
		}
	}
	if (ans == 1e15)cout << -1 << endl;
	else cout << ans << endl;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mkp make_pair
#define f(i,l,h) for(ll i=l;i<h;i++)
#define fr(i,h,l) for(ll i=h;i>=l;i--)

using namespace std;

typedef pair<ll,ll> pll;
const ll INF=(ll)(1e9+7);
typedef vector<ll> vll;

int main()
{
    //cout << "Hello world!" << endl;
    ll k;
    cin>>k;
    string s;
    cin>>s;
    if(s.length()<=k){
        cout<<s<<endl;
    }else{
        cout<<s.substr(0,k)<<"..."<<endl;
    }
}


Measured memory_bytes: 3632
S = gets.strip
T = gets.strip

A = []
(0..(S.size - T.size)).each do |i|
    flag = true
    (0...T.size).each do |j|
        if S[i + j] != "?" && S[i + j] != T[j]
    	    flag = false 
    	    break
    	end 
    end
    if flag
    	ans = S[0...i] + T + S[(i + T.size)...S.size]
    	A << ans.gsub(/\?/, "a")
    end
end
if A.empty?
	puts "UNRESTORABLE"
else
	puts A.min 
end




Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
#define all(n) begin(n), end(n)
const long long INF = numeric_limits<long long>::max();
typedef long long ll;
typedef vector<int> vint;
typedef vector<vector<int>> vvint;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef unsigned long long ull;
template <class T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }

template <typename T, typename... Ts>
auto make_v(size_t a, Ts... ts)
{
    return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template <typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T &t, const V &v) { t = v; }

template <typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T &t, const V &v)
{
    for (auto &e : t)
        fill_v(e, v);
}
ll N,K;
vll imos(vll A)
{
    vll table(N+1);
    for (ll i = 0; i < N; i++)
    {
        table[max(0LL,i-A[i])]++;
        table[min((ll)(N),i+A[i]+1)]--;
    }

//    cout<<table[0]<<" ";
    for (ll i = 1; i < N; i++)
    {
        table[i] += table[i-1];
//        cout<<table[i]<<" ";
    }
//    cout<<endl;
    return table;
}
vll solve(function<vll(vll)> func,vll x)
{
    if(K==1)
    {
        return func(x);
    }
    if(K==0)
    {
        return x;
    }
    if(K%2 == 1)
    {
        K--;
        return func(solve(func,x));
    }
    else
    {
        auto func2 = [&func](vll t){return func(func(t));};
        K/=2;
        return solve(func2,x);
    }
    
}
int main()
{
    
    cin>>N>>K;
    vll A(N);
    for (size_t i = 0; i < N; i++)
    {
        cin>>A[i];
    }
/*    for (size_t i = 0; i < N; i++)
    {
        A = imos(A);
    }
    */
    chmin(K,50LL);
    auto ans = solve(imos,A);
    for (size_t i = 0; i < N; i++)
    {
        cout<<ans[i]<<" ";
    }
    
    
    return 0;
}

Measured memory_bytes: 28452
#include<stdio.h>
#include<stdlib.h>
int main(void){
  int n;
  scanf("%d",&n);
  int w[n],total=0;
  for(int i=0;i<n;i++){
	scanf("%d",&w[i]);
    total+=w[i];
           
  }
  int sum=0,min=1000000;
  for(int i=0;i<n-1;i++){
	for(int j=0;j<=i;j++){
      sum+=w[j];
    }
    if(abs(sum-(total-sum))<min)
      min=abs(sum-(total-sum));
                           sum=0;             }
                                     printf("%d",min);
 return 0;
       
}

Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cassert>
#define int long long
using namespace std;
typedef pair<int, int> P;

int n, k;
P x[100000];

signed main() {
	int i;
	
	cin >> n >> k;
	for (i = 0; i < n; i++) {
		cin >> x[i].first >> x[i].second;
	}
	sort(x, x + n);
	
	int cnt = 0;
	for (i = 0; i < n; i++) {
		cnt += x[i].second;
		if (cnt >= k) {
			cout << x[i].first << endl;
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <string>
using namespace std;
int main(void){
    int n;
    string s,t;
    cin>>n>>s>>t;
    for(int i=0;i<n;i++){
        if(s.substr(i,n-i)==t.substr(0,n-i)){
            cout<<n+i<<endl;
            return 0;
        }
        
    }
    cout<<n*2<<endl;
}


Measured memory_bytes: 256
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include<set>
#include<map>
using namespace std;


int main() {
    int a, b;
    cin >> a >> b;
    if(b%a == 0){
        cout << a+b;
    }
    else
    {
        cout << b-a;
    }
    
    cout << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ii = pair<int, int>;
using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;
#define szof(a) (int)a.size()
#define allof(a) a.begin(), a.end()
#define f first
#define s second
const int MOD = 998244353;
int add(int x, int y) { return (x + y) % MOD; }
int mul(int x, int y) { return 1LL * x * y % MOD; }
int n;
string x;
int f[200005];
int main() {
#ifdef LOCAL
    freopen("data.txt", "r", stdin);
#endif
    cin.sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> x;

    int cnt = 0;
    for (int T = 1; T <= n; ++T) {
        cnt = mul(cnt, 2);
        if (x[T - 1] == '1') ++cnt;
        if (n % T == 0) {
            if ((n / T) % 2 == 0)
                continue;

            f[T] = add(f[T], cnt);
            // tot -= cnt;
            // now compare
            int cur = 0;
            bool ok = true;
            for (int i = 0, j = 0; i < n; ++i, ++j) {
                if (j == T) {
                    j = 0;
                    cur ^= 1;
                }
                int dig = (x[j] - '0') ^ cur;
                if (dig > (x[i] - '0')) {
                    ok = false;
                    break;
                } else if (dig < (x[i] - '0')) {
                    break;
                }
            }
            if (ok) {
                f[T] = add(f[T], 1);
            }
        }
    }
    int ans = 0;
    for (int d = 1; d <= n; ++d) {
        if (!(n % d == 0 && ((n / d) % 2) == 1)) continue;
        for (int y = 3 * d; y <= n; y += 2 * d) {
            f[y] = add(f[y], -f[d]);
        }
        ans = add(ans, mul(f[d], 2 * d));
    }
    if (ans < 0) ans += MOD;
    cout << ans << "\n";
}

Measured memory_bytes: 1300
a, b, m = map(int, input().split())
li_a = list(map(int, input().split()))
li_b = list(map(int, input().split()))
li_c = []
for _ in range(m):
  x, y, c = map(int, input().split())
  x, y = x-1, y-1
  li_c.append(li_a[x]+li_b[y]-c)
li_a.sort()
li_b.sort()
li_c.sort()
ans = min(li_a[0]+li_b[0], li_c[0])
print(ans)


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


struct mint{
    static const long long MOD = 1000000007;

    long long v;

    mint() : v(0) {}
    mint(long long x){
        x = x % MOD;
        if(x < 0){ x += MOD; }
        v = x;
    }
    mint& operator+=(mint a){
        v += a.v;
        if(v >= MOD){ v -= MOD; }
        return *this;
    }
    mint& operator*=(mint a){
        v *= a.v;
        v %= MOD;
        return *this;
    }
    mint& operator-=(mint a){
        v -= a.v;
        if(v < 0){ v += MOD; }
        return *this;
    }
    mint& operator/=(mint a){
        return (*this) *= a.inv();
    }

    mint operator*(mint a) const{
        return mint(v) *= a;
    }

    mint operator+(mint a) const {
        return mint(v) += a;
    }

    mint operator-(mint a) const {
        return mint(v) -= a;
    }

    mint operator/(mint a) const {
        return mint(v) /= a;
    }

    mint pow(long long k) const {
        mint res(1),tmp(v);
        while(k){
            if(k&1) res *= tmp;
            tmp *= tmp;
            k >>= 1;
        }
        return res;
    }
    mint inv(){return pow(MOD - 2); }

    static mint comb(long long n, int k){
        mint res(1);
        for(int i = 0; i < k; ++i){
            res *= mint(n - i);
            res /= mint(i + 1);
        }
        return res;
    }

    static mint factorial(long long n){
        mint res(1);
        for(int i = n; i > 1; --i){
            res *= mint(i);
        }
        return res;
    }

    bool operator<(const mint &a) const {
        return v < a.v;
    };
};

mint operator*(long long l, mint r){ return r * l; }

std::ostream& operator<<(std::ostream& stream, const mint& m){
    stream << m.v;
    return stream;
}

struct mintcomb{
    vector<mint> fact;
    vector<mint> ifact;
    mintcomb(ll n) : fact(n + 1, 1), ifact(n + 1, 1) {
        for(ll i = 2; i <= n; ++i){
            fact.at(i) = fact.at(i - 1) * i;
            ifact.at(i) = fact.at(i).inv();
        }
    }

    mint factorial(ll k) const { return fact.at(k); }
    mint combination(ll k, ll l) const {
        return fact.at(k) * ifact.at(l) * ifact.at(k - l);
    }
};

int main(){
    ll n, k;
    cin >> n >> k;
    mintcomb mc(n);
    mint ans = 0;
    REP(nz, min(n - 1, k) + 1){
        ans += mc.combination(n, nz) * mc.combination(n - 1, n - nz - 1);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3328
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define sz(x) (int)(x.size())
#define fi first
#define se second
#define pii pair<int, int>

vector<vector<int>> g;
vector<bool> visited;
vector<int> red, black;
void dfs(int v, int p) {
  visited[v] = true;
  if (p == 0) {
    red.push_back(v);
  } else {
    black.push_back(v);
  }
  for (auto &u : g[v]) {
    if (!visited[u]) {
      dfs(u, 1 - p);
    }
  }
}
signed main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);
  int n;
  cin >> n;
  g.resize(n + 1);
  visited.assign(n + 1, false);
  for (int i = 1; i < n; i++) {
    int u,v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  dfs(1, 0);
  if (sz(red) > sz(black)) {
    swap(red, black);
  }
  vector<int> ans(n + 1, 0);
  visited.assign(n + 1, false);
  if (sz(red) * 3 <= n) {
    vector<int> v1, v2;
    for (int i = 1; i <= sz(red); i++) {
      v1.push_back(i * 3);
    }
    for (int i = (sz(red) + 1) * 3; i <= n; i += 3) {
      v2.push_back(i);
    }
    for (int i = 1; i <= n; i += 3) {
      v2.push_back(i);
    }
    for (int i = 2; i <= n; i += 3) {
      v2.push_back(i);
    }
    for (int i = 0; i < sz(red); i++) {
      ans[red[i]] = v1[i];
    }
    for (int i = 0; i < sz(black); i++) {
      ans[black[i]] = v2[i];
    }
  } else {
    vector<int> v1, v2;
    for (int i = 1; i <= n; i += 3) {
      v1.push_back(i);
    }
    for (int i = 2; i <= n; i += 3) {
      v2.push_back(i);
    }
    for (int i = 3; sz(v1) < sz(red); i += 3) {
      v1.push_back(i);
    }
    for (int i = (n / 3) * 3; sz(v2) < sz(black); i -= 3) {
      v2.push_back(i);
    }
    for (int i = 0; i < sz(red); i++) {
      ans[red[i]] = v1[i];
    }
    for (int i = 0; i < sz(black); i++) {
      ans[black[i]] = v2[i];
    }
  }
  for (int i = 1; i <= n; i++) {
    cout << ans[i] << " ";
  }
  cout << "\n";
}



Measured memory_bytes: 22764
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string n;
    cin  >>n;
  int s=n.size();
    char c = n[s-1];
  if(c=='2'||c=='4'||c=='5'||c=='7'||c=='9'){
    cout<<"hon"<<endl;
  }
  else if(c=='0'||c=='1'||c=='6'||c=='8'){
    cout<<"pon"<<endl;
  }
  else{
    cout<<"bon"<<endl;
  }
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define ALL(a)  (a).begin(),(a).end()
#define SZ(a) int((a).size())
#define SORT(c) sort((c).begin(),(c).end())
#define MEMSET(v, h) memset((v), h, sizeof(v))
#define sqr(x) ((x) * (x))
#define bit(n) (1LL<<(n))
#define pcnt(x) __builtin_popcountll(x)
#define PB push_back
#define MP make_pair
#define endl "\n"
using Edge = pair<int,int>;
using Graph = vector<vector<Edge>>;
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; }
// ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
// ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

int main() {
  int a,b; cin >> a >> b;
  double ans = 1;
  while(1){
    if(floor(ans * 0.08)==a && floor(ans*0.1)==b){
      cout << ans << endl;
      return 0;
    }
    ans += 1;
    if(ans==1000000) {
    cout << -1 << endl;
    return 0;
  }
  }
  
}



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

int main() {
    char c;
    cin >> c;

    if(c == 'a' || c == 'i' || c == 'u' || c == 'e' || c == 'o') {
        cout << "vowel" << endl;
    } else {
        cout << "consonant" << endl;
    }
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

template <typename TYPE>
void print_vec(const vector<TYPE>& v){
	for(int i=0; i<v.size(); i++){
		cout << v[i] << " ";
	}
	cout << endl;
}

template <typename TYPE>
void print_vec2(const vector<vector<TYPE>>& v){
  cout << endl; cout << "       ";
  for(int i=0; i<v[0].size(); i++) cout << i << "   "; 
  cout << endl;
	for(int i=0; i<v.size(); i++){
		cout << "i=" << i << ":   ";
		for(int j=0; j<v[i].size(); j++){
			if(v[i][j] == 0) cout << "\x1B[0m" << v[i][j] << "   ";
      else cout << "\x1B[31m" << v[i][j] << "   ";//https://stackoverrun.com/ja/q/12618775
		}
		cout << "\x1B[0m" << endl;
	}
}

////////////////////////////////////////////////////////////////

int main(void) {
	ll N, K;
	cin >> N >> K;
	vector<ll> A(N);
	for(int i=0; i<N; i++) cin >> A[i];
	sort(A.begin(), A.end());

	vector<ll> plus, minus;
	for(int i=0; i<N; i++){
		if(A[i]<0) minus.push_back(A[i]);
		else plus.push_back(A[i]);
	}

	const ll MAX = ll(1e18) + 1;
	ll left = -MAX, right = MAX;
	ll mid = (left+right) /2;
	while(left + 1 < right){
		bool ok;
		ll cnt = 0;
		for(int i=0; i<N; i++){
			if(A[i] >= 0){
				int ok_id = -1, bad_id = N;
				while(ok_id+1 < bad_id){
					int center = (ok_id+bad_id)/2;
					if(A[i] * A[center] < mid) ok_id = center;
					else bad_id = center; 
				}
				cnt += ok_id+1;// ok_id+1=bad_idになってるはず
			}
			else{
				int bad_id = -1, ok_id = N;
				while(bad_id+1 < ok_id){
					int center = (ok_id+bad_id) /2;
					if(A[i] * A[center] < mid) ok_id = center;
					else bad_id = center;
				}
				cnt += N - (ok_id);//例：ok_id=N-1なら +1される
			}
			
			if(A[i]*A[i] < mid) cnt--; //自分自身との掛け算はカウントしちゃだめなので，-1する
		}
		cnt /= 2;
		if(cnt < K) ok = true;
		else ok = false;

		if(ok) left = mid;
		else right = mid;
		mid = (left + right) /2;
	}

	cout << left << endl;

}


Measured memory_bytes: 7168
import sys
sys.setrecursionlimit(10**9)
mod = 10**9+7
N = int(input())
G = [[] for i in range(N)]
for i in range(N-1):
    x, y = map(int, input().split())
    G[x-1].append(y-1)
    G[y-1].append(x-1)
    
def dfs(i, pi):
    b = 1
    w = 1
    for ni in G[i]:
        if ni == pi:
            continue
        [nb, nw] = dfs(ni, i)
        b *= nw
        b %= mod
        w *= nw + nb
        w %= mod
    return [b, w]

print(sum(dfs(0, -1))%mod)

Measured memory_bytes: 99760
n,K = map(int,input().split())
d = [[int(i) for i in input().split()] for _ in range(n)]
x = sorted(d,key=lambda x:x[0])
y = sorted(d,key=lambda x:x[1])
ans = float("inf")

for i in range(n):
    for j in range(i+1,n):
        for k in range(n):
            cnt = 0
            for l in range(k,n):
                if x[i][0] <= y[l][0] <= x[j][0]: cnt += 1
                if cnt == K:
                    dx = x[j][0]-x[i][0]
                    dy = y[l][1]-y[k][1]
                    ans = min(ans, dx*dy)
                    break
print(ans)

Measured memory_bytes: 3064
import heapq

nv, ne = map(int, input().split())

edges = [set() for _ in range(nv)]
while ne:
    s, t, w = map(int, input().split())
    edges[s].add((w, t))
    edges[t].add((w, s))
    ne -= 1

cost = 0
queue = list(edges[0])
heapq.heapify(queue)
visited = [False] * nv
visited[0] = True

while queue:
    edge_cost, t = heapq.heappop(queue)
    if visited[t]:
        continue
    visited[t] = True
    cost += edge_cost
    if all(visited):
        break
    for e in edges[t]:
        if not visited[e[1]]:
            heapq.heappush(queue, e)

print(cost)

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

int main() {
    string S;
    int Q;
    cin >> S >> Q;
    bool rev = false;
    string f = "";
    string b = "";
    rep(i, Q) {
        int q = 0;
        cin >> q;
        if (q == 1) {
            rev = !rev;
            continue;
        }
        int F;
        char C;
        cin >> F >> C;
        if (!rev) {
            if (F == 1)
                f = f + C;
            else
                b = b + C;
        } else {
            if (F == 1)
                b = b + C;
            else
                f = f + C;
        }
    }

    string ans = "";
    if (!rev) {
        for (auto e : f)
            ans = e + ans;
        ans = ans + S;
        ans = ans + b;
    } else {
		reverse(all(S));
        for (auto e : b)
            ans = e + ans;
		ans = ans + S;
		ans = ans + f;
        
    }
    cout << ans << endl;
}

Measured memory_bytes: 1836
using System;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = Console.ReadLine().Split(' ');
            var x = int.Parse(input[0]);
            var y = int.Parse(input[1]);

            if (y % 2 == 0 && y >= 2 * x && y <= 4 * x)
                Console.WriteLine("Yes");
            else
                Console.WriteLine("No");
        }

    }
}



Measured memory_bytes: 27532
#include <bits/stdc++.h>
#define mk make_pair
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
int n, m;
int s, a[N], b[N];
int ans, tmp = 1e9;
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", a + i);
		s += a[i];
		a[i] *= n;
	}
	for (int i = 1; i <= n; ++i) {
		if (abs(a[i] - s) < tmp) {
			tmp = abs(a[i] - s);
			ans = i;
		}
	}
	cout << ans - 1 << endl;
} 

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
#define rep(i, a, b) for (int i = a; i < b; ++i)

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

if(a+b==15) cout<<'+'<<endl;
else if(a*b==15) cout << '*' <<endl;
else cout << 'x' <<endl;
return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using static System.Console;
using static System.Math;

namespace AtTest.ABC_144
{
    class C
    {
        static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(OpenStandardOutput()) { AutoFlush = false };
            SetOut(sw);

            Method(args);

            Out.Flush();
        }

        static void Method(string[] args)
        {
            long n = ReadLong();
            long res = long.MaxValue;
            for(long i = 1; i * i <= n; i++)
            {
                if (n % i == 0)
                {
                    long tmp = i - 1 + n / i - 1;
                    res = Min(res, tmp);
                }
            }
            WriteLine(res);
        }

        private static string Read() { return ReadLine(); }
        private static char[] ReadChars() { return Array.ConvertAll(Read().Split(), a => a[0]); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }
    }
}


Measured memory_bytes: 13140
#include <cstdio>
#include <algorithm>
#include <functional>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)

int main() {
	int ary[10];
	rep(i,10) {
		scanf(" %d", &ary[i]);
	}
	sort(ary, ary + 10, greater<int>());
	rep(i,3) {
		printf("%d\n", ary[i]);
	}
	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#include <regex>
#ifdef _DEBUG
#include "debug.h"
#endif
#define int ll
#define FOR(i, s, e) for (int i = int(s); i < int(e); ++i)
#define REP(i, e) FOR(i, 0, e)
#define mkpr make_pair
#define mktp make_tuple
#define tv(tp, i) get<(i)>(tp)
#define CLEAR(obj) obj = decltype(obj)()
#define var auto
#define OUT(type) type &
#define IN(type) const type &
#define self (*this)
#define in :
#define True true
#define False false
using namespace std; using str = string; using cstr = const str;
using ll = long long; using ull = unsigned long long; using cint = const int; using cll = const ll;
using vi = vector<int>; using vvi = vector<vi>; using vl = vector<ll>; using vvl = vector<vl>;
using vb = vector<bool>; using vvb = vector<vb>; using vd = vector<double>; using vvd = vector<vd>;
using vc = vector<char>; using vvc = vector<vc>; using vs = vector<string>;
using pii = pair<int, int>; using pll = pair<ll, ll>; using pdd = pair<double, double>; using psl = pair<string, ll>;
using tiii = tuple<int, int, int>; using tlll = tuple<ll, ll, ll>;
static const int MGN = 10; static const int ARYSZ_MAX = (int)1e7;
static const ll LINF = LLONG_MAX/2;
#ifdef int
static const int INF = LINF;
#else
static const int INF = INT_MAX/2;
#endif
static double EPS = 1e-9;
static inline bool DBLEQ(double a, double b) {return abs(a - b) < EPS;}
static inline void EPR(str msg) {cerr << msg << endl;}
static inline void AST(bool exp, str msg) {if(!exp){EPR(msg);} assert(exp);}
static inline void TAST(bool exp, str msg) {if(!exp){EPR(msg);} while(!exp){}}


int32_t main(int32_t argc, char* argv[]) {
    cin.tie(0);
    ios::sync_with_stdio(false);
#ifdef IMPORT_SAMPLE
    vs args(argv, argv+argc);
    string sample = make_sample(args, "sample-1");
    ifstream ifs(sample); cin.rdbuf(ifs.rdbuf());
#endif


    int H, W; cin >> H >> W;
    vs S(H); REP(i, H) cin>>S[i];

    int black = 0;
    REP(i, H)
        REP(j, W) if (S[i][j] == '#') black++;

    int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
    queue<pii> que;
    que.push(mkpr(0, 0));
    vvi dist(H, vi(W, INF));
    vvi vis(H, vi(W, 0));
    dist[0][0] = 0;

    while(!que.empty()) {
        var pr = que.front(); que.pop();
        int x = pr.first, y = pr.second;
        vis[x][y] = 1;
        if(x == H-1 and y ==  W-1) break;

        REP(i, 4) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 or H <= nx or ny < 0 or W <= ny) continue;
            if (S[nx][ny] == '#') continue;
            if (dist[nx][ny] != INF) continue;

            //dist[nx][ny] = min(dist[nx][ny], dist[x][y] + 1);
            dist[nx][ny] = dist[x][y] + 1;
            que.push(mkpr(nx, ny));
        }
    }

    int ans = -1;
    if (vis[H-1][W-1] == 1) {
        ans = H*W - black - (dist[H-1][W-1] + 1);
    }
    cout << ans << endl;


    return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
int main() {
  cin.tie(0); ios_base::sync_with_stdio(false);
  int N, L; cin >> N >> L;
  vector<string> S(N); for (auto& s : S) cin >> s;
  sort(S.begin(), S.end());
  for (auto& s : S) cout << s;
  cout << endl;
  return 0;
}


Measured memory_bytes: 256
N = int(input())

A = list(range(4, 101, 4))
B = list(range(7, 101, 7))

is_made = False

if N in A or N in B:
    is_made = True
else:
    for a in A:
        for b in B:
            if a+b > N:
                break
            elif a+b == N:
                is_made = True
                break

if is_made:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 9196
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()
#define LL long long

using namespace std;


//BEGIN CUT HERE
struct Dice{
    int s[6];

    Dice(int top,int front,int right){
        s[0]=top,s[1]=front,s[2]=right,s[3]=7-front,s[4]=7-right,s[5]=7-top;
    }


    void roll(int dir){
        //0:?\\?????? 1:????????? 2:????????? 3:????????????
        vector<int> v;
        switch(dir){
            case 0:
                v = {0,1,5,3};break;
            case 1:
                v = {0,4,5,2};break;
            case 2:
                v = {0,2,5,4};break;
            case 3:
                v = {0,3,5,1};break;
        }
        for(int i=0;i<v.size()-1;i++)swap(s[v[i]],s[v[i+1]]);
    }

    int top(){return s[0];}
    int front(){return s[1];}
    int right(){return s[2];}
    int back(){return s[3];}
    int left(){return s[4];}
    int down(){return s[5];}
};

//END CUT HERE

int main(){

    Dice dice(1,2,3);
    map<int,int> mp;
    REP(i,6){
        int c;cin>>c;
        mp[i+1]=c;
    }
    string s;cin>>s;

    REP(i,s.size()){
        switch(s[i]){
            case 'N':dice.roll(0);break;
            case 'E':dice.roll(1);break;
            case 'W':dice.roll(2);break;
            case 'S':dice.roll(3);break;
        }
    }
    cout<<mp[dice.top()]<<endl;

    return 0;
}

Measured memory_bytes: 3152
#include <iostream>
#include <list>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
typedef long long lli;
typedef vector<lli> vll;
typedef vector<bool> vbl;
typedef vector<vector<lli> > mat;
typedef vector<vector<bool> > matb;
typedef vector<string> vst;
typedef pair<lli,lli> pll;
typedef pair<double,double> pdd;

lli v,e;
mat m;

lli x,y,c;
const lli INF = 1000000000000;

int main(){
    cin >> v >> e;
    m = mat(v,vll(v,INF));
    for(lli i = 0;i < v;i++) m[i][i] = 0;
    for(lli i = 0;i < e;i++){
        cin >> x >> y >> c;
        m[x][y] = c;
    }
    for(lli i = 0;i < v;i++) for(lli j = 0;j < v;j++) for(lli k = 0;k < v;k++){
        if(m[j][i] == INF || m[i][k] == INF) continue;
        m[j][k] = min(m[j][k],m[j][i]+m[i][k]);
    }
    for(lli i = 0;i < v;i++) if(m[i][i] < 0){
        cout << "NEGATIVE CYCLE" << endl;
        return 0;
    }
    for(lli i = 0;i < v;i++){
        for(lli j = 0;j < v;){
            if(m[i][j] == INF) cout << "INF";
            else cout << m[i][j];
            if(++j < v) cout << " ";
            else cout << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 3224
#include <iostream>
#include <iomanip>
#include <stdio.h>
using namespace std;

int main()
{
	int a[1000];
	int b[1000];
	int c[1000];
	char op[1000];
	
	int i = 0;
	while(1){
		cin >> a[i] >> op[i] >> b[i];
		
		switch(op[i]){
			case '+':
				c[i] = a[i] + b[i];	break;
			case '-':
				c[i] = a[i] - b[i];	break;
			case '*':
				c[i] = a[i] * b[i];	break;
			case '/':
				c[i] = a[i] / b[i];	break;
		}
		if(op[i] == '?') break;
		i++;
	}
	
	for(i=0; op[i] != '?'; i++)
		cout << c[i] << endl;
	
	return 0;
}



Measured memory_bytes: 3096
ab=[list(map(int, input().split())) for _ in range(3)]
tmp=[0]*4
for i in range(3):
    tmp[ab[i][0]-1]+=1
    tmp[ab[i][1]-1]+=1
tmp2=sorted(tmp)
print("YES" if tmp2==[1, 1, 2, 2] else "NO")


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

int main(){
    const int MAX_N = 10000;
    int n;
    int a[MAX_N];
    int b[MAX_N];
    int aPoint=0;
    int bPoint=0;
    
    
    while(true){
        cin >> n;
        if(n==0){
            break;
        }
        for(int i=0;i<n;i++){
            cin >> a[i];
            cin >> b[i];
            if (a[i] > b[i]){
                aPoint += a[i]+b[i];
            }else if (a[i]<b[i]){
                bPoint += a[i]+b[i];
            }else{
                aPoint += a[i];
                bPoint += b[i];
            }
        }
        cout << aPoint << " ";
        cout << bPoint << "\n";
        aPoint = 0;
        bPoint = 0;
    }
}

Measured memory_bytes: 3152