akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#include<stdlib.h>
int asc(const void* a, const void* b)
{
	if (*(int*)a > * (int*)b)return 1;
	if (*(int*)a < *(int*)b)return -1;
	return 0;
}
int main()
{
	long long int n;
	scanf("%lld", &n);
	long long int i;
	int a[100005], b[100005], c[100005];
	for (i = 0; i < n; i++)
		scanf("%d", &a[i]);
	for (i = 0; i < n; i++)
		scanf("%d", &b[i]);
	for (i = 0; i < n; i++)
		scanf("%d", &c[i]);
	qsort(a, n, sizeof(int), asc);
	qsort(b, n, sizeof(int), asc);
	qsort(c, n, sizeof(int), asc);
	long long int ans = 0;
	long long int aa, cc;
	long long int min, mid, max;
	for (i = 0; i < n; i++)
	{
		if (b[i] <= a[0])
			continue;
		min = 0;
		max = n;
		while (max - min > 1)
		{
			mid = (max + min) / 2;
			if (a[mid] < b[i])
				min = mid;
			else
				max = mid;
		}
		aa = min + 1;
		if (b[i] >= c[n - 1])
			break;
		min = 0;
		max = n;
		while (max - min > 1)
		{
			mid = (max + min) / 2;
			if (c[mid] <= b[i])
				min = mid;
			else
				max = mid;
		}
		if (b[i] < c[0])
			cc = n;
		else
			cc = n - max;
		ans += aa * cc;
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 1788
n=int(input())
import numpy as np
f=[]
for i in range(n):
    f.append(list(map(int,input().split())))
p=[]
for i in range(n):
    p.append(list(map(int,input().split())))
x=np.asarray(f)
mx=-10**9
for i in range(1,2**10):
    y=np.asarray([int(x) for x in list(format(i,'010b'))])
    z=x*y
    can=np.sum(z,axis=1)
    c=0
    for j in range(n):
        c += p[j][can[j]]
    mx=max(c,mx)
print(mx)

Measured memory_bytes: 27192
#include<bits/stdc++.h>
using namespace std;
 
#define cinsc ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(0);
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define FOR(i,k,n)  for(int64 i=k;i<(int64)n;i++)
#define FOREACH(it, l) for (auto it = l.begin(); it != l.end(); it++)
#define FOREACHr(it, l) for (auto it = l.rbegin(); it != l.rend(); it++)
#define IN(A, B, C) assert( B <= A && A <= C)
#define MP make_pair
#define PB push_back
#define INF (int)1e9
#define EPS 1e-9
#define PI 3.1415926535897932384626433832795
#define MOD 1000000007
#define read(type) readInt<type>()
#define SQ(x) ((x)*(x))
const double pi=acos(-1.0);
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef map<int,int> MPII;
typedef set<int> SETI;
typedef multiset<int> MSETI;
typedef long int int32;
typedef unsigned long int uint32;
typedef long long int int64;
typedef unsigned long long int  uint64;
 
//ONLINE_JUDGE   LOCAL
 
int64 powr(int64 x,int64 y,int64 p)  
{  
    int res = 1;    
    x = x % p; 
    if (x == 0) return 0;
    while (y > 0){   
        if (y & 1)  
            res = (res*x) % p;   
        y = y>>1; 
        x = (x*x) % p;  
    }  
    return res;  
} 
 
void  in_o(){
#ifndef LOCAL
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
#endif
	cinsc;
}


int main(){
	//in_o();
	int64 x;
	cin>>x;
	int64 a=1;
	while(2*x>a*(a-1))
		a++;
	cout<<a-1<<endl;
	return 0;
}


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

using namespace std;

#define MAX 1000
#define INF 1e9

int V;
struct State{
  int x, y;
};

vector<State> vec;

double Dis(State a, State b){
  return sqrt(pow((a.x-b.x),2.) + pow(a.y-b.y,2.));
}

double cost[MAX][MAX];

void dijkstra(int s, int t){
  double dist[MAX];
  bool used[MAX];
  int prev[MAX];

  fill(dist, dist+MAX, INF);
  memset(used,false,sizeof(used));
  memset(prev,-1,sizeof(prev));
  dist[s] = 0;

  while(true){
    int v = -1;
    for(int u = 0 ; u < V ; u++){
      if(!used[u] && (v == -1 || 
                      dist[u] < dist[v])){
        v = u;
      }
    }

    if(v == -1){
      break;
    }else{
      used[v] = true;
    }

    for(int u = 0 ; u < V ; u++){
      if(dist[u] > dist[v] + cost[u][v] && cost[u][v] <= 50){
        dist[u] = dist[v] + cost[u][v];
        prev[u] = v;
      }
    }
  }

  if(dist[t] == INF){
    cout << "NA" << endl;
  }else{
    vector<int> path;
    for(int i = t ; i != -1 ; i = prev[i]){
      path.push_back(i);
    }
    reverse(path.begin(), path.end());
    
    int len = path.size();
    for(int i = 0 ; i < len ; i++){
      cout << path[i]+1 << (i == len-1 ? '\n' : ' ');
    }
  }
}

int main(){
  int n, start, goal, num;
  State s;

  while(cin >> V, V){
    State dist[MAX];

    vec.clear();
    fill(cost[0],cost[V],INF);
    for(int i = 0 ; i < V ; i++){
      cin >> num >> s.x >> s.y;
      vec.push_back(s);
      dist[num-1] = s;
    }

    for(int i = 0 ; i < V-1 ; i++){
      for(int j = i+1 ; j < V ; j++){
        cost[i][j] = cost[j][i] = 
          Dis(dist[i],dist[j]);
      }
    }
 
    cin >> n;
    for(int i = 0 ; i < n ; i++){
      cin >> start >> goal;
      start--, goal--;
      dijkstra(start, goal);
    }
  }
  
  return 0;
}

Measured memory_bytes: 2028
def main():
  N = int(input())
  A = [int(input()) for _ in range(N)]
  s = sum(A)
  if s%10 != 0:
    print(s)
    return
  m = 10000
  for a in A:
    if a%10 != 0:
      m = min(m, a)
  print(s - m if m != 10000 else 0)
  return

if __name__ == '__main__':
  main()

Measured memory_bytes: 3060
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
 
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define _D(p) std::cout<<"L"<<__LINE__<<" : " #p " = "<<(p)<<std::endl;
#define _D2(p,q) std::cout<<"L"<<__LINE__<<" : " #p " = "<<(p) << ", " #q " = "<<(q)<<std::endl;
#define _DN(v) std::cout<<"L"<<__LINE__<<" : " #v " = ["; rep(i,(v).size()) {std::cout<<v[i]<<(i==v.size()-1?"":", ");}std::cout<<"]"<<std::endl;
#define _DNN(v) std::cout<<"L"<<__LINE__<<" : " #v " = [" << std::endl; rep(i,(v).size()) {std::cout<<"    [";rep(j,(v)[0].size()){std::cout<<v[i][j]<<(j==v[0].size()-1?"":", ");}std::cout<<"],"<<std::endl;}std::cout<<"]"<<std::endl;
 
using namespace std;
 
typedef    long long          ll;
typedef    unsigned long long ull;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      pii;
 
const int INF=1<<29;
const double EPS=1e-9;
 
const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};
int main(int argc, char const *argv[]) {
    int N, M;
    cin >> N >> M;
    int t = M * 1900 + (N - M) * 100;
    cout << ((1 << M) - 1) * t + t << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<algorithm>
#include<functional>
#include<utility>
#include<bitset>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<cstdio>

using namespace std;

#define REP(i,n) for(int i=0;i<int(n);i++)
#define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
typedef long long ll;
typedef pair<int,int> P;

ll dp[110][100010],w[110],v[110];

int main(void){
	          ll i,j;

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

	          ll N,W;
	          cin >> N >> W;
	          for(i=0;i<N;i++) cin >> w[i] >> v[i];

	          for(i=0;i<N;i++){
	        	  for(j=0;j<=W;j++){
	        		  if(j<w[i]) dp[i+1][j]=dp[i][j];
	        		  else dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i]);
	        	  }
	          }

	          cout << dp[N][W] << endl;

	          return 0;
}


Measured memory_bytes: 79360
#include <bits/stdc++.h>
using namespace std;
int n, q, x, y;
int main() {
	scanf("%d%d", &n, &q);
	for (int i = 0; i < q; i++) {
		scanf("%d%d", &x, &y);
		while (true) {
			if (x > y) {
				swap(x, y);
			}
			if (x == y || n == 1) {
				break;
			}
			y = (y + n - 2) / n;
		}
		printf("%d\n", x);
	}
	return 0;
}

Measured memory_bytes: 1280
#include<bits/stdc++.h>
#define LL long long
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPA(i,n) for(int i=1;i<(n);++i)
#define PII pair<int,int>
#define PLI pair<long long, int>
#define PLL pair<long long, long long>
#define MOD ((int)1e9 + 7)
#define INF ((int)1e9)
#define INFLL ((LL)1e18)
#define ALL(x) (x).begin(),(x).end()
#define CTOI(x) (x - 'A') 
#define ctoi(x) (x - 'a')
#define BIT(x) (1 << (x))
using namespace std;

LL modinv(LL a){
    LL b = MOD, u = 1, v = 0;
    while(b){
        LL t = a / b;
        a -= t * b;swap(a, b);
        u -= t * v;swap(u, v);
    }
    u%=MOD;
    if(u < 0) u += MOD;
    return u;
}

LL exp(LL a, LL b){
    LL res = 1;
    LL sum = a;
    while(b){
        if(b&1)res = (res * sum) % MOD;
        sum = (sum * sum) % MOD;
        b>>=1;
    }
    return res;
}

int count(int x){
    int res = 0;
    while(x){
        res += x & 1;
        x>>=1;
    }
    return res;
}

vector<int> getsosu(int N){
    vector<int> res;
    vector<int> check(N+1, true);
    for(int i=2;i<=N;++i){
        if(check[i]){
            res.push_back(i);
            for(int j=i*2;j<=N;j+=i){
                check[j]=false;
            }
        }
    }
    return res;
}

int main(){
    int N, M;
    while(cin >> N >> M && N){
        int r;
        cin >> r;
        vector<vector<PII> > student(M+1);
        REP(i, r){
            int a, b, c, d;
            cin >> a >> b >> c >> d;
            student[c].push_back(PII(a, d * 2 - 1));
        }
        int q;
        cin >> q;
        REP(i, q){
            int s, e, m;
            cin >> s >> e >> m;
            vector<int> imos(1261, 0);
            REP(j, student[m].size()){
                imos[student[m][j].first]+=student[m][j].second;
            }
            int ans = 0;
            int sum = 0;
            REP(j, 1261){
                sum += imos[j];
                if(s <= j && j < e && sum > 0)++ans;
            }
            cout << ans << endl;
        }
    }
    return 0;
}



Measured memory_bytes: 3324
#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if (x < y) x = y; }

int main() {
	int N; int A; int B;
	while (~scanf("%d%d%d", &N, &A, &B)) {
		vector<int> X(N);
		for (int i = 0; i < N; ++i)
			scanf("%d", &X[i]);
		ll ans = 0;
		rep(i, N - 1)
			ans += min((ll)A*(X[i + 1] - X[i]), (ll)B);
		printf("%lld\n", ans);
	}
	return 0;
}


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

int d;

int main ()
{
	cin >> d;
	
	if ( d == 25 )
	   cout << "Christmas" << endl;
	else if ( d == 24 )
	   cout << "Christmas Eve" << endl;
	else if ( d == 23 )
	   cout << "Christmas Eve Eve" << endl;
	else
	   cout << "Christmas Eve Eve Eve" << endl;
	
	return 0;
	
}

Measured memory_bytes: 256
N = int(input())
S = input()
 
left = 0
right = 1
max_length = 0
 
while left < N:
    if right - left > N - right:
        break
    serch_str = S[left:right]
    if serch_str in S[right:]:
        max_length = max(max_length, len(serch_str))
        right += 1
    else:
        left += 1
 
print(max_length)

Measured memory_bytes: 41196
#include <iostream>

int main(){
	int N;
	int a[200];
	std::cin>>N;
	int min = 1000;
	for(std::size_t i=0;i<N;i++){
		std::cin>>a[i];
	}

	for(std::size_t i=0;i<N;i++){
		int count = 0;
		while(a[i]%2 != 1){
			a[i] /= 2;
			count += 1;
		}
		if(count == 0){
			min = count;
			break;
			}
		if(count <= min){
			min = count;
		}
	}
	std::cout<<min;
	return 0;

}


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

int main(){
  ll w,h,n;cin >> w >> h >> n;
  vector<string> field(h);
  rep(i,h) field.at(i).resize(w);
  rep(i,h) rep(j,w) field.at(i).at(j) = 'o';

  rep(i,n){
    ll x,y,a;cin >> x >> y >> a;
    if( a == 1 ){
      rep(j,h){
        for(ll k=0;k<x;++k) field.at(j).at(k) = 'x';
      }
    }else if( a == 2 ){
      rep(j,h){
        for(ll k=x;k<w;++k) field.at(j).at(k) = 'x';
      }
    }else if( a == 3 ){
      for(ll j=1;j<=y;++j){
        rep(k,w) field.at(h-j).at(k) = 'x';
      }
    }else if( a == 4 ){
      for(ll j=h-y-1;j>=0;--j){
        rep(k,w) field.at(j).at(k) = 'x';
      }
    }
  }

  ll ans = 0;
  rep(i,h) rep(j,w) if( field.at(i).at(j) == 'o' ) ans++;

  cout << ans << endl;

  // rep(i,h){
  // 	rep(j,w) cout << field.at(i).at(j) << " ";
  // 	cout << endl;
  // }

  return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
using P = pair <int, int>;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
ll gcd(ll a,ll b) {return  b ? gcd(b,a%b) : a;}
const long long INF = 1LL << 60;
const int mod = 1000000007;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};

int main() {
     int n,k;
     cin >> n >> k;
     vector<int> p(n);
     rep(i,n) cin >> p[i];  
     sort(p.begin(),p.end());
     int ans = 0;
     rep(i,k){
          ans+=p[i];
     }     
     cout << ans <<endl;
}

Measured memory_bytes: 3616
using System;
class Program
{
	static void Main(string[] args)
	{
		// 整数の入力
		int a = int.Parse(Console.ReadLine());
      	if (a % 2 == 0) {
        	Console.WriteLine(a/2-1);
        } else {
        	Console.WriteLine(a/2);
        }
	}
}

Measured memory_bytes: 13140
p = 10**9+7
def power_func(a,n):
    bi=str(format(n,"b"))#2進表現に
    res=1
    for i in range(len(bi)):
        res=(res*res) %p
        if bi[i]=="1":
          res=(res*a) %p
    return res
g1,g2,inverse = [1, 1],[1, 1],[0, 1]
for i in range(2,2*(10**5)+1):
    g1.append((g1[-1]*i)%p)
    inverse.append((-inverse[p%i]*(p//i))%p)
    g2.append((g2[-1]*inverse[-1])%p)
n,a,b= map(int,input().split())
comnk=1
temp1=-1
for i in range(b):
    comnk=(((comnk*(n-i))%p)*inverse[i+1])%p
    if i==a-1:temp1=(power_func(2,n)-1+p-comnk)%p
print((temp1 + p - comnk) % p)

Measured memory_bytes: 27120
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
#define rep(i,n) for(int i = 0; i < ((int)(n)); i++)   // 0-indexed昇順

int main() {
    int N; cin >> N;
    int i = 0;
    while (i * 1000 < N) i++;
    cout << i * 1000 - N << endl;

}


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

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;

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

    int ans = 0;
    while (n != 0) {
        n /= k;
        ans++;
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())

X = [a,b,c,d,e]

order_list = []
for x in X:
    priority = x % 10
    if priority == 0:
        priority = 10
    order_list.append([x, priority])

order_list.sort(key=lambda order: order[1])

total_time = 0
for time, priority in order_list[1:]:
    plus10 = 0
    if time % 10 > 0:
        plus10 = 10
    actual_time = time//10*10 + plus10
    total_time += actual_time
    #print([time, priority], actual_time, total_time)

order = order_list.pop(0)
time = order[0]
total_time += time

print(total_time)


Measured memory_bytes: 38256
#include<bits/stdc++.h>
using namespace std;
struct UnionFind
{
  vector<int> Parent;
  UnionFind(int n):Parent(n,-1){}
  int Root(int y){return Parent.at(y)<0?y:Parent.at(y)=Root(Parent.at(y));}
  bool Unite(int x,int y)
  {
    if((x=Root(x))==(y=Root(y)))return true;
    else
    {
      if(-Parent.at(x)<-Parent.at(y))swap(x,y);
      Parent.at(x)+=Parent.at(y);
      Parent.at(y)=x;
      return false;
    }
  }
  int Size(int y){return -Parent.at(Root(y));}
};
int main()
{
  int a,b,c,d,N,M,K;
  cin>>N>>M>>K;
  UnionFind uf(N);
  vector<int> known(N,0);
  while(M--)
  {
    cin>>a>>b;
    a--,b--;
    uf.Unite(a,b);
    known.at(a)++,known.at(b)++;
  }
  while(K--) 
  {
    cin>>c>>d;
    c--,d--;
    if(uf.Root(c)==uf.Root(d))known.at(c)++,known.at(d)++;
  }
  for(int i=0;i<N;i++)cout<<(uf.Size(i)-known.at(i)-1)<<" ";
  return cout<<endl,0;
}

Measured memory_bytes: 1664
S = input()
a = int(S[:2])
b = int(S[2:])
 
if 1 <= a and a <= 12 and 1 <= b and b <= 12:
    print("AMBIGUOUS")
elif 1 <= a and a <= 12 and (b > 12 or b < 1):
    print("MMYY")
elif (a > 12 or a < 1) and 1 <= b and b <= 12:
    print("YYMM")
else:
    print("NA")

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

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

    cout << (abs(a - c) <= d or (abs(a - b) <= d and 
            abs(b - c) <= d) ? "Yes" : "No") << endl;

    return 0;
}

Measured memory_bytes: 256
import sys
import math
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
import itertools
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()

ans = N % K
if ans > abs(K - ans):
    ans = abs(K - ans)
print(ans)


Measured memory_bytes: 17060
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

A = INT()
B = INT()

if A > B :
    print("GREATER")
elif A < B:
    print("LESS")
else:
    print("EQUAL")

Measured memory_bytes: 5144
# import 周り
from fractions import gcd

# 定数関係
mod = 10 ** 9 + 7

# 補助関数
def inv(a):
    b, u, v = mod, 1, 0
    while b != 0:
        t = a // b
        a, b = b, a - t * b
        u, v = v, u - t * v
    return u

if __name__ == '__main__':
    #入力関係
    n = int(input())
    A = list(map(int, input().split()))

    U, V = 0, 1
    for ele in A:
      V *= ele // gcd(V, ele)# LCMを計算
      U += inv(ele)
    V %= mod
    print(U * V % mod)


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

typedef long long ll;
typedef long double ld;

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

	ld l;
	cin >> l;
	cout << (l/3)*(l/3)*(l/3);
    return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <math.h>
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <algorithm>
#include <numeric>
#include <stdio.h>
#include <vector>
#include <map>
#include <queue>

using namespace std;
typedef long long ll;

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

int main() {

    ll K,T;
    cin >> K >> T;
    ll a[T];
    rep(i,T) cin >> a[i];
    sort(a,a+T);
    ll s = a[T-1]-1-(K-a[T-1]);
    ll out = 0;
    if(s>0) out = s;
    cout << out << endl;
    return 0;
}


Measured memory_bytes: 3588
#include <iostream>
#include <string>
#include <cstdlib>

using namespace std;

int main(){
  	string s;
  	cin >> s;
  	int count=0;
  	int n = int(s.size());
  	for(int i=0;i<n;i++){
      	count += s[i]-48;
    }
  	if(count%9 == 0) cout << "Yes" << endl;
  	else cout << "No" << endl;
}

Measured memory_bytes: 3748
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
from fractions import gcd
from functools import reduce
 
N,M,*A = map(int,read().split())
 
# 「奇数倍」に帰着
A = [x >> 1 for x in A]
 
def merge(a,b):
    g = gcd(a,b)
    a //= g; b //= g
    if a % 2 == 0:
        return 0
    if b % 2 == 0:
        return 0
    n = a * b * g
    if n > 10 ** 9:
        return 0
    return n
 
x = reduce(merge, A)
if x == 0:
    answer = 0
else:
    answer = (M//x) - (M//(x+x))
 
print(answer)

Measured memory_bytes: 14504
#include "bits/stdc++.h"
using namespace std;
#define repi(i,a,b) for(int i=(a), i##_len=(b); i<i##_len; ++i)
#define rep(i,n) repi(i,0,n)
#define repi_(i,a,b) for(int i=(a), i##_len=(b); i<=i##_len; ++i)
#define rep_(i,n) repi_(i,0,n)
#define all(x) (x).begin(),(x).end()
#define vsort(v) sort((v).begin(), (v).end())
#define gsort(v) tsort(v); reverse((v).begin(), (v).end())
#define vrev(v) reverse((v).begin(), (v).end())
#define siz(v) ((int)(v).size())
#define ers(v, n) (v).erase((v).begin() + n)
#define cnt(v, n) count(all(v), n)
#define vmin(v) *min_element(v.begin(), v.end())
#define vmax(v) *max_element(v.begin(), v.end())
#define el "\n"
#define co(x) cout<<(x)<<el
#define coc(c, a, b) if(c)co((a));else co((b))
#define cosp(x) cout<<(x)<<' '
#define YES(c) coc(c,"YES", "NO")
#define Yes(c) coc(c,"Yes", "No")
#define yes(c) coc(c,"yes", "no")
#define POSSIBLE(c) coc(c, "POSSIBLE", "IMPOSSIBLE")
#define Possible(c) coc(c, "Possible", "Impossible")
#define possible(c) coc(c, "possible", "impossible")
#define inf INT_MAX
#ifdef tqktmp_2
#define gc() getchar(); getchar()
#else
#define gc() 1
#endif


typedef long long lint;

lint dx[8] = { 0,1,1,1,0,-1,-1,-1 },
dy[8] = { 1,1,0,-1,-1,-1,0,1 };

template<class T>inline bool maxi(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>inline bool mini(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }



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

	lint x; cin >> x;
	lint ctr = 1, now = 0;
	while (1) {
		now += ctr;
		if (now >= x) {
			co(ctr);
			gc();
			return 0;
		}
		++ctr;
	}
	gc();
}

Measured memory_bytes: 256
#include<stdio.h>
int main(){
  int a,b,c=0;
  scanf("%d %d",&a,&b);
  if(a>b){
    c+=a;
    a--;
  }
  else{
    c+=b;
    b--;
  }
  if(a>b){
    c+=a;
    a--;
  }
  else{
    c+=b;
    b--;
  }
  printf("%d\n",c);
  return 0;
}

Measured memory_bytes: 128
n,k = map(int, raw_input().split())
s = raw_input()
cd = 0
d = None
for l in s:
	if d != l:
		cd +=1
		d = l
score = 0
for u,v in zip(s,s[1:]):
	if u == v:
		score +=1

while(k and cd > 1):

	if cd > 2:
		score += 2 
		cd -= 2
	elif cd == 2:
		score +=1
		cd -= 1
	k -=1
print score

Measured memory_bytes: 46316
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep2(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep_inv(i, n, m) for(int i = (int)(n); i > (int)(m); i--)
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vc = vector<char>;
using vvl = vector<vl>;
using vvc = vector<vc>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;

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

  cout << N / 2 + N % 2 << "\n";
  
  return 0;
}


Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define M 1000000007
#define ll long long
#define REP(i,a,b) for(ll i=a;i<b;i++)
#define REPI(i,a,b) for(ll i=b-1;i>=a;i--)
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define MT make_tuple
#define G(a,b) get<a>(b)
#define VI vector<int>
#define VLL vector<long long>
 
#define o_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define o_setll tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
//member functions :
//1. order_of_key(k) : number of elements strictly lesser than k
//2. find_by_order(k) : k-th element in the set
 
ll modI(ll a, ll m);
ll gcd(ll a, ll b);
ll powM(ll x, unsigned ll y, unsigned ll m);
void pairsort(int a[], int b[], int n);
void pairsortll(ll a[],ll b[],ll n);
ll logint(ll x,ll y);
 
 
ll gcd(ll x,ll y)
{
    if(x==0) return y;
    return gcd(y%x,x);
}
 
ll powM(ll x,ll y,ll m)
{
    if(y==0) return 1;
    ll p=powM(x,y/2,m)%m;
    p=(p*p)%m;
    return (y%2==0)?p:(x*p)%m;
}
 
ll modI(ll a, ll m)
{
    ll m0=m,y=0,x=1;
    if(m==1) return 0;
    while(a>1)
    {
        ll q=a/m;
        ll t=m;
        m=a%m;
        a=t;
        t=y;
        y=x-q*y;
        x=t;
    }
    if(x<0) x+=m0;
    return x;
}
 
void pairsort(int a[],int b[],int n)
{
    pair<int,int> v[n];
    REP(i,0,n)
    {
        v[i].F=a[i];
        v[i].S=b[i];
    }
    sort(v,v+n);
    REP(i,0,n)
    {
        a[i]=v[i].F;
        b[i]=v[i].S;
    }
}
 
void pairsortll(ll a[],ll b[],ll n)
{
    pair<ll,ll> v[n];
    REP(i,0,n)
    {
        v[i].F=a[i];
        v[i].S=b[i];
    }
    sort(v,v+n);
    REP(i,0,n)
    {
        a[i]=v[i].F;
        b[i]=v[i].S;
    }
}
 
ll logint(ll x,ll y)
{
    ll ans=0;
    ll a=1;
    for(ll i=0;i<=x;i++)
    {
        if(x<a)
        {
            return ans;
        }
        ans++;
        a*=y;
    }
    return -1;
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    /*
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    */
 
    ll q=1;
    //cin>>q;
    while(q--)
    {
        ll n,W;
        cin>>n>>W;
        ll dp[n][W+1];
        ll w[n],v[n];

        REP(i,0,n)
        {
            cin>>w[i]>>v[i];
        }

        REP(j,0,W+1)
        {
            dp[0][j]=-1;
        }

        dp[0][0]=0;
        if(w[0]<=W)
            dp[0][w[0]]=v[0];

        REP(i,1,n)
        {
            REP(j,0,W+1)
            {
                dp[i][j]=-1;
                if(dp[i-1][j]!=-1)
                    dp[i][j]=max(dp[i][j],dp[i-1][j]);
                if(w[i]<=j)
                    dp[i][j]=max(dp[i][j],v[i]+dp[i-1][j-w[i]]);
            }
        }
        ll ans=0;
        REP(j,0,W+1)
        {
            ans=max(ans,dp[n-1][j]);
        }
        cout<<ans;
    }
 
    return 0;
}


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

#define MAX_E 2001
#define MAX_V 1001
#define INF 1LL << 60

// 頂点fromから頂点toへのコストcostの辺
struct edge { long long from, to, cost; };
edge es[MAX_E]; // 辺
long long d[MAX_V]; // 最短距離
long long V, E; // Vは頂点数、Eは辺数
bool negative[MAX_V];
// s番目の頂点から各頂点への最短距離を求める
void shortest_path(long long s) {
	for (long long i = 0; i < V; i++) d[i] = INF;
	d[s] = 0;
	for (long long i = 0; i < V; i++) {
		bool update = false;
		for (long long j = 0; j < E; j++) {
			edge e = es[j];
			if (d[e.from] != INF && d[e.to] > d[e.from] + e.cost) {
				d[e.to] = d[e.from] + e.cost;
				update = true;
			}
		}
		if (!update) break;
	}
}

// trueなら負の閉路が存在する
void find_negative_loop() {
	memset(d, 0, sizeof(d));
	for (int i = 0; i < V; i++) negative[i] = false;
	for (int i = 0; i < V; i++) {
		for (int j = 0; j < E; j++) {
			edge e = es[j];
			if (d[e.to] > d[e.from] + e.cost) {
				d[e.to] = d[e.from] + e.cost;
				// n回目にも更新があるなら負の閉路が存在する
				if (i == V - 1) negative[e.to] = true;
			}
		}
	}
}

void solve(long long N, long long M, vector<long long> a, vector<long long> b, vector<long long> c){
	V=N; E=M;
	find_negative_loop();
	if (negative[N-1]) printf("inf\n"); else {
		shortest_path(0);
		printf("%lld\n",-d[N-1]);
	}

}

int main(){
	long long N;
	long long M;
	scanf("%lld",&N);
	scanf("%lld",&M);
	vector<long long> b(M-1+1);
	vector<long long> c(M-1+1);
	vector<long long> a(M-1+1);
	for(int i = 0 ; i <= M-1 ; i++){
		scanf("%lld",&a[i]);
		scanf("%lld",&b[i]);
		scanf("%lld",&c[i]);
		es[i] = (edge) {a[i]-1,b[i]-1,-c[i]};
	}
	solve(N, M, a, b, c);
	return 0;
}


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

using ll=long long;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll n, m;
  cin >> n >> m;
  vector<tuple<ll,ll>> memo;
  rep(i,n) {
    ll a, b;
    cin >> a >> b;
    memo.push_back(make_tuple(a,b));
  }
  sort(memo.begin(),memo.end());
  ll need = m;
  ll ans = 0;
  rep(i,n){
    if(need >= get<1>(memo[i])) {
      ans += get<0>(memo[i])*get<1>(memo[i]);
      need -=get<1>(memo[i]);
    }else{
      ans += get<0>(memo[i])*need;
      need = 0;
    }
    if(need == 0) break;
  }
   cout << ans << endl; 
}

Measured memory_bytes: 2420
//minamoto
#include<bits/stdc++.h>
#define R register
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
const int P=998244353;
inline void upd(R int &x,R int y){(x+=y)>=P?x-=P:0;}
inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}
inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}
inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}
int ksm(R int x,R int y){
	R int res=1;
	for(;y;y>>=1,x=mul(x,x))(y&1)?res=mul(res,x):0;
	return res;
}
const int N=5e5+5;
int bin[N],c[N],x[N],y[N],id[N],b[N],m,n,res;
inline void chg(R int x){for(;x<=n;x+=x&-x)++c[x];}
inline int query(R int x){R int res=0;for(;x;x-=x&-x)res+=c[x];return res;}
inline bool cmpx(const int &a,const int &b){return x[a]<x[b];}
inline bool cmpy(const int &a,const int &b){return y[a]<y[b];}
int main(){
	scanf("%d",&n);
	bin[0]=1;fp(i,1,n)bin[i]=mul(bin[i-1],2);
	fp(i,0,n)bin[i]=dec(bin[i],1);
	fp(i,1,n)id[i]=i,scanf("%d%d",&x[i],&y[i]),b[i]=y[i];
	fp(i,1,n)res=dec(res,mul(add(bin[i-1],bin[n-i]),2));
	sort(b+1,b+1+n);fp(i,1,n)y[i]=lower_bound(b+1,b+1+n,y[i])-b;
	sort(id+1,id+1+n,cmpx);
	memset(c,0,sizeof(c));
	fp(i,1,n){
		R int c=query(y[id[i]]);
		upd(res,bin[c]),upd(res,bin[i-1-c]);
		chg(y[id[i]]);
	}
	memset(c,0,sizeof(c));
	reverse(id+1,id+1+n);
	fp(i,1,n){
		R int c=query(y[id[i]]);
		upd(res,bin[c]),upd(res,bin[i-1-c]);
		chg(y[id[i]]);
//		printf("%d %d\n",i,add(bin[c],bin[i-1-c]));
	}
	upd(res,mul(n,bin[n]));
	printf("%d\n",res);
	return 0;
}

Measured memory_bytes: 9600
#include<stdio.h>
#include<string.h>

int main()
{
    int flg=0;
    char s[200],p[100];
    scanf("%s", &s);
    scanf("%s", &p);
    int tr = strlen(s);
    for(int j=0;j<tr;j++){
          s[tr+j] = s[j];
    }
    for(int i=0;i<=strlen(s);i++){
        if(p[0] == s[i]){
            for(int tmp=0;tmp<strlen(p);tmp++){
                if(s[i+tmp]==p[tmp]){
                    flg = 1;
                }else {
                    flg = 0;
                    break;
                }
            }
            if(flg == 1){
                break;
            }
        }
    }
    if(flg == 1){
        printf("Yes\n");
    }else {
        printf("No\n");
    }
    return 0;
}


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

#define PI 3.14159265359
#define INF 1e9
#define LINF 1e18
#define IMOD 1000000007 
#define irep(i,n) for(int i = 0; i < (int)(n); i++)
#define irep2(i,a,n) for(int i = (int)(a); i <= (int)(n); i++)
#define lrep(i,n) for(long long  i = 0; i < (long long)(n); i++)
#define lrep2(i,a,n) for(long long i = (long long)(a); i <= (long long)(n); i++)

#define irrep(i,n) for(int i = (int)(n-1); i > -1; i--)
#define irrep2(i,a,n) for(int i = (int)(n); i >= (int)(a); i--)

typedef long long ll;
typedef std::vector<char> v_char;
typedef std::vector<v_char > v2_char;
typedef std::vector<double> v_double;
typedef std::vector<v_double > v2_double;
typedef std::vector<int> v_int;
typedef std::vector<v_int > v2_int;
typedef std::vector<ll> v_ll;
typedef std::vector<v_ll > v2_ll;
typedef std::vector<std::string> v_string;
typedef std::vector<v_string > v2_string;
typedef std::vector<bool> v_bool;
typedef std::vector<v_bool > v2_bool;
typedef std::pair<ll, ll> pll;
typedef std::pair<int, int> pii;

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

ll burger[50][2];

ll dfs_all(int n) 
{
    if(n == 0) {
        return 1;
    }
    burger[n][0] = 2 * dfs_all(n-1)+3;
    return burger[n][0];
}

ll dfs_beaf(int n) 
{
    if(n == 0) { return 1; }
    burger[n][1] = 2 * dfs_beaf(n-1)+1;
    return burger[n][1];
}

ll dfs_eat(int n, ll x)
{
    if(n == 0) { return 1; } 

    if(x == 1) {
        return 0;
    } else if(1 + burger[n-1][0] >= x) {

        return dfs_eat(n-1, x-1);

    } else if(1 + burger[n-1][0] + 1 == x) {

        return burger[n-1][1] + 1;

    } else if(2 + 2*burger[n-1][0] >= x) {

        return burger[n-1][1] + 1 + dfs_eat(n-1, x-burger[n-1][0]-2);

    } else {
        return burger[n][1];
    }
}

int main(void)
{
    ll n, x;
    cin >> n >> x;
    //cin >> n;
        
    burger[0][0] = 1;
    burger[0][1] = 1;

    dfs_all(n);
    dfs_beaf(n);

    //irep(i, n+1) { printf("%lu,%lu\n", burger[i][0], burger[i][1]); }

    cout << dfs_eat(n,x);
    
    return 0;
}
/** tcoder **/


Measured memory_bytes: 256
import sys
input = sys.stdin.buffer.readline
import numpy as np

def main():
    N,M = map(int,input().split())
    a = np.array(input().split(),np.int64)
    a = np.sort(a)
    cum = np.zeros(N+1,dtype=int)
    cum[1:] = np.cumsum(a)
    
    l,r = -1,10**6+1
    while r-l > 1:
        mid = (l+r)//2
        ab_mid = (N-np.searchsorted(a,mid-a,side="left")).sum()
        if ab_mid >= M:
            l = mid
        else:
            r = mid

    pos_rev = np.searchsorted(a,r-a,side="left")
    count = (N-pos_rev).sum()
    ans = (cum[-1]-cum[pos_rev]).sum()
    ans += (a*(N-pos_rev)).sum()
    ans += (M-count)*l
        
    print(ans)

if __name__ == "__main__":
    main()


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

int main()
{
    string s;
    cin >> s;
    int cnt;
    
    if (s[0] == '1')
        cnt++;
    if (s[1] == '1')
        cnt++;
    if (s[2] == '1')
        cnt++;
        
    std::cout << cnt << std::endl;
}

Measured memory_bytes: 3592
N,A=map(int,raw_input().split())
x=[0]+map(int,raw_input().split())
#print x
y=map(lambda i:i-A, x)
#print y

max_x=max(max(x),A)
#print max_x

dp=[[0]*(2*N*max_x+1) for i in range(N+1)]

for j in range(N+1):
	for t in range(2*N*max_x):
		if j==0 and t==N*max_x:
			dp[j][t]=1
		elif j>=1 and (t-y[j]<0 or t-y[j]>2*N*max_x):
			dp[j][t]=dp[j-1][t]
		elif j>=1 and t-y[j]>=0 and 2*N*max_x>=t-y[j]: 
			dp[j][t]=dp[j-1][t]+dp[j-1][t-y[j]]
		else:
			dp[j][t]=0

print dp[N][N*max_x]-1
			
		

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

using namespace std;
#define ll long long

int main(){
  ll n;
  string s,t;
  cin >> n >> s >> t;
  if(s == t){
    cout << n << endl;
    return 0;
  }
  ll i;
  ll cnt = 0;
  for(i = 1; i <= n; i++){
    if(s.substr(n-i, i) == t.substr(0,i)){
      cnt = i;
    }
  }
  cout << n * 2 - cnt<< endl;
}


Measured memory_bytes: 256
use strict;
use warnings;

chomp(my $n = <>);
my @v = split /\s/, <>;
my @c = split /\s/, <>;

my $value = 0;
my $cost = 0;

for (my $i = 0; $i < $n; $i++) {
  if ($v[$i] > $c[$i]) {
  	$value += $v[$i];
  	$cost += $c[$i];
  }
}

print $value - $cost, "\n";



Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define REP(i,n) for(ll i=0;i<n;i++)
#define FOR(i,n1,n2) for(ll i=n1;i<n2;i++)
#define bFOR(i,n1,n2) for(ll i=n1;i>=n2;i--)
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
typedef long long int ll;
typedef pair<ll,ll> Pi;
typedef tuple<ll,ll,ll> Tu;
const int INF=(ll)(1LL<<30)-1;
const double INFd=100000000000.0;
const double PI=3.14151926535;
const ll INFl=(ll)9223372036854775807;
const int MAX=10000;
const ll MOD=(ll)1e9+7;
const ll tMOD=(ll)998244353;
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 dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};
int mdx[8]={0,1,0,-1,1,1,-1,-1},mdy[8]={-1,0,1,0,1,-1,1,-1};


template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

int h,w;
char s[110][110];
int d[110][110];

int main(){
    cin>>h>>w;
    REP(i,h)
        REP(j,w)cin>>s[i][j];
    d[0][0]=0;
    REP(i,h)
        REP(j,w){
            if(i==0&&j==0)continue;
            if(i==0){
                d[i][j]=d[i][j-1]+(s[i][j]=='#'&&s[i][j-1]=='.');
            }else if(j==0){
                d[i][j]=d[i-1][j]+(s[i][j]=='#'&&s[i-1][j]=='.');
            }else{
                d[i][j]=min(d[i][j-1]+(s[i][j]=='#'&&s[i][j-1]=='.'),d[i-1][j]+(s[i][j]=='#'&&s[i-1][j]=='.'));
            }
        }
    
    cout<<d[h-1][w-1]+(s[0][0]=='#'?1:0)<<endl;
    return 0;
}

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


int topdown(int*a,int*dp,int n)
{
	dp[n-1]=0;
	dp[n-2]=abs(a[n-1]-a[n-2]);

	for(int i=n-3;i>=0;i--)
	{
		dp[i]=min(abs(a[i]-a[i+1])+dp[i+1] , abs(a[i]-a[i+2])+dp[i+2]);
	}
	return dp[0];
}

int main()
{  	
  	ios_base::sync_with_stdio(0);            
	cin.tie(NULL);
	cout.tie(NULL);
  	int dp[100000];
	int n,a[100000];
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>a[i];

	cout<<topdown(a,dp,n);

	return 0;
}


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

using namespace std;
inline void prep ()
{
  cin.tie (0);
  cin.sync_with_stdio (0);
};
const double pi = acos(-1.);
//printf(%.12lf\n,mid);
// __builtin_popcount(int) count 1's in binary
// get decimal part of number
/*
double intpart;
double thiss = modf((double)(n*m)/(double)k, &intpart);
*/
// round = (int)(num+.5)
long long mod = 1000000007;

long long mymod(long long num){
  if (num< 0 && !(num%mod == 0)){
    if (mod == 1){
      return 0;
    }
    return mod-abs(num)%mod;
  }else{
    return num%mod;
  }
}

/*string sentence = And I feel fine...;
    istringstream iss(sentence);
*/  

double eps = .000000001;
const long long maxx = 1000000000000000000LL;
int main(){
  prep();
  int n, m, s, t;
  cin >> n >> m >> s >>t;
  long long dist2a[n+1];
  long long dist2b[n+1];
  for (int i=1; i<=n; i++){
      dist2a[i] = maxx;
      dist2b[i] = maxx;
  }
  vector<pair<int, pair<int, int> > > graph[n+1];
  for (int i=0; i<m; i++){
      int a, b, x, y;
      cin >> a >> b >> x >> y;
      graph[a].push_back({b, {x, y}});
      graph[b].push_back({a, {x, y}});
  }
  queue<int> q;
  q.push(s);
  dist2a[s] = 0;
  dist2b[t] = 0;
  while (!q.empty()){
      int front = q.front();
      q.pop();
      for (int i=0; i<graph[front].size(); i++){
          int node = graph[front][i].first;
          long long dist = graph[front][i].second.first;
          if (dist2a[front]+dist < dist2a[node]){
              dist2a[node] = dist2a[front]+dist;
              q.push(node);
          }
      }
  }
  queue<int> temp;
  q = temp;
  q.push(t);
  while (!q.empty()){
      int front = q.front();
      q.pop();
      for (int i=0; i<graph[front].size(); i++){
          int node = graph[front][i].first;
          long long dist = graph[front][i].second.second;
          if (dist2b[front]+dist < dist2b[node]){
              dist2b[node] = dist2b[front]+dist;
              q.push(node);
          }
      }
  }
  pair<long long, long long> dists[n];
  for (int i=1; i<=n; i++){
      dists[i-1] = {dist2a[i]+dist2b[i], i};
  }
  sort(dists, dists+n);
  int cur = 0;
  for (int i=0; i<n; i++){
      while (dists[cur].second <= i){
          cur++;
      }
      cout << 1000000000000000LL-dists[cur].first << '\n';
  }
  return 0; 
}

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

typedef long long int ll;
#define INF 1999999999
#define MODA 1000000007

int main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s1, s2;
    cin >> s1 >> s2;
    int count = 0;
    for(int i = 0; i < 3; i++)
    {
        if(s1[i] == s2[i])
        {
            count++;
        }
    }
    cout << count << endl;
    
    return 0;
}


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

int main(){
  string s,t;
  cin>>s>>t;
  if(s.size()+1==t.size()){
  for(int a=0;a<s.size();a++){
    if(s[a]!=t[a]){
      cout<<"No"<<endl;
      return 0;
    }
  }
    cout<<"Yes"<<endl;
  }
  else{
    cout<<"No"<<endl;
  }
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll,ll>;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep2(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
const ll INF = 1LL<<60;
const ll MOD = 1e9+7;


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n; cin>>n;
    string s;cin>>s;
    vector<ll> r(n+1,0), g(n+1,0), b(n+1,0);
    for(int i=n-1; i>=0; i--){
        r[i]=r[i+1];
        g[i]=g[i+1];
        b[i]=b[i+1];
        if(s[i]=='R')r[i]++;
        if(s[i]=='B')b[i]++;
        if(s[i]=='G')g[i]++;
    }
    ll ans = 0;
    for(int i=0; i<n; i++){
        for(int j=i+1; j<n; j++){
            if(s[i]==s[j])continue;
            int k = 2*j-i;
            if((s[i]=='R'&&s[j]=='B')||(s[i]=='B'&&s[j]=='R')){
                ans += g[j+1];
                if(k<n&&s[k]=='G')ans--;
            }
            if((s[i]=='R'&&s[j]=='G')||(s[i]=='G'&&s[j]=='R')){
                ans += b[j+1];
                if(k<n&&s[k]=='B')ans--;
            }
            if((s[i]=='G'&&s[j]=='B')||(s[i]=='B'&&s[j]=='G')){
                ans += r[j+1];
                if(k<n&&s[k]=='R')ans--;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3752
#define rep(i,a,b) for (int i = (a); i < (b); i++)
#define _USE_MATH_DEFINES
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <math.h>
#include <complex>
#include <cassert>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> p;
typedef complex<double> com;
const int mod = 1e9 + 7;
const int MOD = 998244353;
const ll INF = 1e18;



int main() {
	int h, w; cin >> h >> w;
	vector<string> a(h);
	vector<vector<ll>> memo(h);
	rep(i, 0, h) memo[i].resize(w, -1);
	rep(i, 0, h) cin >> a[i];
	queue<p> q;
	rep(i, 0, h)rep(j, 0, w) {
		if (a[i][j] == '#') {
			q.push({ i,j });
			memo[i][j] = 0;
		}
	}
	while (!q.empty()) {
		p s = q.front(); q.pop();
		int dx[4] = { -1,1,0,0 }, dy[4] = { 0,0,1,-1 };
		rep(i, 0, 4) {
			int x = s.first + dx[i], y = s.second + dy[i];
			if (x < 0 || x >= h || y < 0 || y >= w) continue;
			if (a[x][y] == '#'||memo[x][y]>=0) continue;
			q.push({ x, y });
			memo[x][y] = memo[s.first][s.second] + 1;
		}
	}
	ll ans = -1;
	rep(i,0, h) {
		rep(j,0, w) {
			ans = max(ans, memo[i][j]);
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 25524
import java.util.*;

public class Main {
    public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int N = sc.nextInt();
	int ac=0,wa=0,tle=0,re=0;
	for (int i=0;i<N;i++) {
	    String s = sc.next();
	    if (s.equals("AC")) ac++;
	    else if (s.equals("WA")) wa++;
	    else if (s.equals("TLE")) tle++;
	    else { re++; }
	}
	System.out.println("AC x "+ac);
	System.out.println("WA x "+wa);
	System.out.println("TLE x "+tle);
	System.out.print("RE x "+re);
    }
}


Measured memory_bytes: 58504
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int MAXN = 1e5 + 5;
vector<int> v(MAXN);

main() {
	int n;
	cin >> n;
	vector<int> a(n);
	int ans = 0;
	for (int i = 0; i < n; i++){
		cin >> a[i];
		if (a[i] == i + 1)
            ans++;
	}
	for (int i = 1; i < n; i++){
        if (a[i] == i + 1) {
            if (a[i - 1] == i){
                ans--;
                swap(a[i], a[i - 1]);
            }
        }
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 1792
#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int sts[100001],dep[100001],pre[100001],dist[100001];
bool contains[100001];
vector<int> mp[100001];
int dfs(int k,int oppo,int p,int curd)
{
	if (k==oppo)
		contains[k]=true;
	dep[k]=curd;
	int ret=1;
	for (size_t i=0;i<mp[k].size();++i)
		if (mp[k][i]!=p)
		{
			ret+=dfs(mp[k][i],oppo,k,curd+1);
			if (contains[mp[k][i]])
				contains[k]=true;
		}
	return sts[k]=ret;
}
int main()
{
	int n;
	scanf("%d",&n);
	for (int i=1;i<n;++i)
	{
		int t1,t2;
		scanf("%d%d",&t1,&t2);
		mp[t1].push_back(t2);
		mp[t2].push_back(t1);
	}
	queue<int> q;
	q.push(1);
	memset(dist,-1,sizeof(dist));
	dist[1]=0;
	pre[1]=-1;
	while (!q.empty())
	{
		int f=q.front();
		q.pop();
		for (size_t i=0;i<mp[f].size();++i)
			if (dist[mp[f][i]]==-1)
			{
				q.push(mp[f][i]);
				dist[mp[f][i]]=dist[f]+1;
				pre[mp[f][i]]=f;
			}
	}
	vector<int> path;
	for (int j=n;j!=-1;j=pre[j])
		path.push_back(j);
	reverse(path.begin(),path.end());
	int e1=path[(path.size()-1)/2],e2=path[(path.size()+1)/2];
	vector<int> tmp;
	for (size_t i=0;i<mp[e1].size();++i)
		if (mp[e1][i]!=e2)
			tmp.push_back(mp[e1][i]);
	mp[e1]=tmp;
	tmp.clear();
	for (size_t i=0;i<mp[e2].size();++i)
		if (mp[e2][i]!=e1)
			tmp.push_back(mp[e2][i]);
	mp[e2]=tmp;
	int siz1=dfs(e1,-1,-1,-1),siz2=dfs(e2,-1,-1,-1);
	printf("%s",siz1>siz2?"Fennec":"Snuke");
	return 0;
}


Measured memory_bytes: 11640
A,B,M=map(int,input().split())

X=[10**10]+list(map(int,input().split()))
Y=[10**10]+list(map(int,input().split()))

K=min(X)+min(Y)

for _ in range(M):
    x,y,c=map(int,input().split())
    K=min(K,X[x]+Y[y]-c)
print(K)


Measured memory_bytes: 98620
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 998244353;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-11;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
typedef pair<ld, ld> LDP;
int main() {
	string s; cin >> s; int out = 0;
	rep(i, 4) {
		if (s[i] == '+')out++;
		else out--;
	}
	cout << out << endl;
	return 0;
}

Measured memory_bytes: 256
import math
a,b,x=map(int,input().split())

"""
平面で考える　
こぼれるときに水が台形になってるなら三角形にする
（直角）三角形の長さを求めてhttps://keisan.casio.jp/exec/system/1259903491　にある計算をする
"""
s=x/a#平面化

if a*b==s:
    print(0)
    exit()

if a*b/2 < s:  #台形
    a1=a
    b1=b-(s/a*2-b)


else: #三角形
    a1= s*2/b 
    b1=b
#print(a1,b1)
ans=math.atan(b1/a1)#サイトの計算
#print(ans)
print(ans*(180.0/math.pi))#ラジアンを角度変換する

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

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

    for(int i = k; i < n; i++){
        if (A[i] > A[i-k])cout << "Yes" << endl;
        else cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 3672
S = input()

decAC = False
declow = False
if S[0] == "A" and S[2:-1].count("C") == 1:
    decAC = True

cnt = 0
for ss in S:
    if ss.islower():
        cnt += 1
if cnt == len(S)-2:
    declow = True
    
if decAC and declow:
    print("AC")
else:
    print("WA")

Measured memory_bytes: 3060