akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a,a+n);
    float val=a[0];
    for(int i=1;i<n;i++){
        val=(val+a[i])/2;
    }
    cout<<val<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <string>
#include <iostream>
using namespace std;
long long n, power[19];
long long check(long long x) {
	long long ret = 0, d = to_string(x).size();
	if (d != 1) ret += 5;
	for (int i = 2; i < d; i++) ret += power[i - 2] * i * 48;
	ret += ((x - power[d - 1] + 1) - (x / 3 - (power[d - 1] - 1) / 3) - (x / 5 - (power[d - 1] - 1) / 5) + (x / 15 - (power[d - 1] - 1) / 15)) * d;
	return ret + (x / 3 + x / 5) * 4;
}
int main() {
	cin >> n;
	power[0] = 1;
	for (int i = 1; i < 19; i++) power[i] = power[i - 1] * 10;
	long long l = 1, r = power[17];
	while (r - l > 1) {
		long long m = (l + r) / 2;
		if (check(m) <= n) l = m;
		else r = m;
	}
	long long d = n - check(l - 1); string ret;
	for (long long i = l; i < l + 20; i++) {
		if (i % 15 == 0) ret += "FizzBuzz";
		else if (i % 3 == 0) ret += "Fizz";
		else if (i % 5 == 0) ret += "Buzz";
		else ret += to_string(i);
	}
	cout << ret.substr(d - 1, 20) << endl;
	return 0;
}

Measured memory_bytes: 3268
/*
 * http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_B&lang=jp
 */
import java.util.*;
import java.util.Arrays;

public class Main {
	
	boolean binSearch(int[] s, int x, int a, int b) {
		int left = 0;
		int right = s.length;
		while (left < right) {
			int mid = (left + right) / 2;
			if (s[mid] == x) return true;
			else if (s[mid] > x) right = mid;
			else left = mid + 1;
		}
		return false;
	}
	
	void run() {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] s = new int[n];
		for (int i = 0; i < n; i++) {
			s[i] = sc.nextInt();
		}
		int q = sc.nextInt();
		int[] t = new int[q];
		for (int i = 0; i < q; i++) {
			t[i] = sc.nextInt();
		}
		Arrays.sort(s);
		
		int cnt = 0;
		for (int i = 0; i < q; i++) {
			if (binSearch(s, t[i], 0, s.length - 1)) cnt++;
		}
		System.out.println(cnt);
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		new Main().run();
	}

}



Measured memory_bytes: 69496
n,m,*A=map(int,open(0).read().split());l=3*m;D=[0]*l;S=0
for a,b in zip(A,A[1:]):
 b+=m*(b<a);k=b-a;S+=k
 if k>1:D[a+2]+=1;D[b+1]-=k;D[b+2]+=k-1
exec("for i in range(1,l):D[i]+=D[i-1]\n"*2);print(S-max(D[a]+D[a+m]for a in A))

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

int main(){
    int_fast64_t N, p, m(0), s(0);
    cin >> N;
    for(int i = 0; i < N; ++i){cin >> p; m = max(m, p); s += p;}
    cout << s - m / 2 << endl;
    return 0;
}


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

const int MAX = 510000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main()
{
  int h,w,a,b;
  cin >> h >> w >> a >> b;
  long long ans=0;
  COMinit();
  for(int i=b;i<w;i++){
    ans += ( (COM(h-a-1+i,i)) * (COM(a+w-i-2,w-i-1)) )%1000000007;
  }
  cout<< ans%1000000007 <<endl;
}


Measured memory_bytes: 12160
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
#
# Created: Jul, 12, 2020 15:51:30 by Nobody
# $Author$
# $Date$
# $URL$
__giturl__ = "$URL$"


from collections import defaultdict
from sys import stdin
input = stdin.readline


def main():
  N, M = list(map(int, input().split()))
  A = sorted(list(map(int, input().split())))
  new = defaultdict(int)
  for _ in range(M):
    B, C = map(int, input().split())
    new[C] += B
  for x in A:
    new[x] += 1
  new = reversed(sorted([(k, v) for k, v in new.items()], key=lambda x: x[0]))
  ans = []
  for k, v in new:
    for i in range(v):
      ans.append(k)
      if len(ans) >= N:
        print(sum(ans))
        return
  print(sum(ans))

  # times = N
  # prev = 0
  # for k, v in new:
  #   idx = bisect.bisect_left(A[prev:], k) + prev
  #   times = v
  #   for i in range(idx):
  #     if not v:
  #       break
  #     times -= 1
  #     A[i] = k
  #   prev = min(prev+v, idx)


if(__name__ == '__main__'):
  main()


Measured memory_bytes: 126884
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
using namespace std;
const int MaxN = 1e5;
char a[105],b[105];

int main()
{
	int n,p,q;
	while(~scanf("%s",a))
	{
		scanf("%s",b);
		n = strcmp(a,b);
		p = strlen(a);
		q = strlen(b);
		if(q < p) printf("GREATER\n");
		else if(q > p) printf("LESS\n");
		else if(q == p)
		{
			if(n > 0) printf("GREATER\n");
			else if(n < 0) printf("LESS\n");
			else printf("EQUAL\n");
		}
	}
	return 0;
}

Measured memory_bytes: 128
# AGC009A - Multiple Array
# greedy algorithm
import sys
input = sys.stdin.readline

def main():
    n = int(input())
    A = tuple(tuple(map(int, input().split())) for _ in range(n))
    ans = 0
    for i, j in A[::-1]:  # # decide from the last one
        ans += -(i + ans) % j
    print(ans)


if __name__ == "__main__":
    main()

Measured memory_bytes: 17380
def dissatisfy(c, last, d, v):
    ans = 0
    for i in range(0, 26):
        if (i != v - 1):
            ans += c[i] * (d - last[i])
    return ans


def main():
    D = int(input())
    c = list(map(int, input().split()))
    last = [0] * 27
    s = list()
    ans = 0

    for d in range(0, D):
        s.append(list(map(int, input().split())))
    for d in range(1, D + 1):
        v = int(input())
        ans += s[d-1][v-1]
        ans -= dissatisfy(c, last, d, v)
        for j in range(0, 27):
            if j == v - 1:
                last[j] = d
        print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 9276
//Utkarsh.25dec
#include <bits/stdc++.h>
#include <chrono>
#include <random>
#define ll long long int
#define ull unsigned long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define rep(i,n) for(ll i=0;i<n;i++)
#define loop(i,a,b) for(ll i=a;i<=b;i++)
#define vi vector <int>
#define vs vector <string>
#define vc vector <char>
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
#define max3(a,b,c) max(max(a,b),c)
#define min3(a,b,c) min(min(a,b),c)
#define deb(x) cerr<<#x<<' '<<'='<<' '<<x<<'\n'
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// ordered_set s ; s.order_of_key(val)  no. of elements strictly less than val
// s.find_by_order(i)  itertor to ith element (0 indexed)
typedef vector<vector<ll>> matrix;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=500023;
bool vis[N];
vector <int> adj[N];
void solve()
{
    ll n;
    cin>>n;
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        if((i%3)==0)
            continue;
        if((i%5)==0)
            continue;
        ans+=i;
    }
    cout<<ans<<'\n';
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int T=1;
    //cin>>T;
    int t=0;
    while(t++<T)
    {
        //cout<<"Case #"<<t<<":"<<' ';
        solve();
        //cout<<'\n';
    }
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}

Measured memory_bytes: 15524
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
#include <memory>
#include <regex>
using namespace std;



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

	vector<long long int> a(n);

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

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

	if (n % 2 == 1) {
		long long int b = a[n / 2];
		long long int ans = 0;
		for (int i = 0; i < n; i++) {
			ans += abs(a[i] - b);
		}
		cout << ans << endl;
		return 0;
	}
	else {
		long long int b1 = a[n / 2];
		long long int b2 = a[(n - 1) / 2];
		long long int ans1 = 0, ans2 = 0;
		for (int i = 0; i < n; i++) {
			ans1 += abs(a[i] - b1);
			ans2 += abs(a[i] - b2);
		}
		cout << min(ans1, ans2) << endl;
		return 0;
	}
	


	return 0;
}


Measured memory_bytes: 1792
#include<stdio.h>
int main(){
  long int a,b,ans;
  scanf("%ld%ld",&a,&b);
  while(a>=b)
    a=a%b;
  if(a>b/2)
    ans=b-a;
  else ans=a;
  printf("%ld",ans);
  return 0;
  }

Measured memory_bytes: 128
#include<stdio.h>
int main(){
  int i,j,k,x[150],y[150],a,t,r;
  int X[]={ 0, 1, 0,-1};
  int Y[]={ 1, 0,-1, 0};
  char d[14][14]={0};
  while(scanf("%s",d[1]+1)!=EOF){
    for(i=2;i<13;i++)scanf("%s",d[i]+1);
    for(i=a=1;i<=12;i++){
      for(j=1;j<=12;j++){
	if(d[i][j]!='1')continue;
	d[i][j]=0;
	x[t=0]=j;
	y[t  ]=i;
	a++;
	for(r=1;r-t;t++){
	  for(k=0;k<4;k++){
	    if(d[y[t]+Y[k]][x[t]+X[k]]=='1'){
	      x[r]=x[t]+X[k];
	      y[r]=y[t]+Y[k];
	      d[y[r]][x[r++]]=0;
	    }
	  }
	}
      }
    }
    printf("%d\n",a-1);
  }
  return 0;
}
    

Measured memory_bytes: 540
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cstring>
#include <cmath>
#include <stack>
#include <iomanip>
#include <tuple>
#include <functional>
#include <cfloat>
#include <map>

//LLONG_MAX
#define int long long
#define CONTAINS(v,n) (find((v).begin(), (v).end(), (n)) != (v).end())
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
#define ARY_SORT(a, size) sort((a), (a)+(size))
#define MAX(a,b) (((a) > (b)) ? (a) : (b))
#define MIN(a,b) (((a) < (b)) ? (a) : (b))
#define REMOVE(v,a) (v.erase(remove((v).begin(), (v).end(), (a)), (v).end()))
#define REVERSE(v) (reverse((v).begin(), (v).end()))
#define LOWER_BOUND(v,a) (lower_bound((v).begin(), (v).end(), (a)))
#define UPPER_BOUND(v,a) (upper_bound((v).begin(), (v).end(), (a)))
#define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define CONTAINS_MAP(m, a) (m).find((a)) != m.end()
using namespace std;

char S[2000];
int w;

signed main()
{
	cin >> S;
	cin >> w;
	int len = strlen(S);
	for (int i = 0; i < len; i++)
	{
		if (i % w == 0)
		{
			cout << S[i];
		}
	}
	cout << endl;
}







Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define reduce200ms ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define dofloat cout<<fixed<<setprecision(6)
#define pb push_back
#define mp make_pair
#define x first
#define y second
#define bitcount _builtin_popcount
#define fill(var,val) memset(var,val, sizeof var)
#define rep(i,a,b) for(auto i=a;i<b;++i)
#define per(i,a,b) for(auto i=a;i>b;--i)
#define elif else if
#define all(vec) vec.begin(),vec.end()
#define rall(vec) vec.rbegin(),vec.rend()
/*
    #ifdef DEBUG
         #define debug(args...)            {dbg,args; cerr<<endl;}
    #else
        #define debug(args...)
    #endif
    struct debugger
    {
        template<typename T> debugger& operator , (const T& v)
        {
            cerr<<v<<" ";
            return *this;
        }
    } dbg;
*/
using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
typedef long double ld;
typedef vector<long long> vl;
typedef pair<long long,long long> pll;
typedef vector<pair<long long,long long> > vll;

const long long MOD=1000000007;
const long long MAX=100005;
const long double PI=3.14159265359;
const long double G=9.807;
const long long INF=1e18;
const long double EPS=1e-6;

long long gcd(long long a,long long b){return b?gcd(b,a%b):a;}
long double dist(long long a,long long b,long long c,long long d){return sqrt( ((a)-(c))*((a)-(c))+((b)-(d))*((b)-(d)) );}
long long min(long long a,long long b,long long c){return min(c,min(a,b));}
long long max(long long a,long long b,long long c){return max(c,max(a,b));}
bool isprime(long long a){
if(a==2)return 1;
if(!(a&1))return 0;
for(ll i=3;i*i<=a;i+=2){
	if(a%i==0)return 0;
}
return 1;
}
long long mpow(long long base,long long exponent,long long modulus){
if(modulus==1)return 0;
long long result = 1;
base=base%modulus;
while(exponent){
		if(exponent%2 == 1)
			result=(result*base)%modulus;
		exponent=exponent>>1;
		base=(base*base)%modulus;
	}
return result;
}
/*template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;*/

int ds(int m){
	int ret=0;
	while(m){
		ret+=m%10;
		m/=10;
	}
	return ret;
}
int n,ans=INT_MAX;
int main(){reduce200ms;
cin>>n;
rep(i,1,n){
	ans=min(ans,ds(i)+ds(n-i));
}
cout<<ans<<'\n';
return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define PI 3.1415926535897
using namespace std;
typedef long long ll;
const int INF = 1000000000;
const ll LINF = 1000000000000000000; //1e18
const double EPS = 1e-10;

int main(void)
{
    string w;
    cin >> w;

    unordered_map<char, int> often;
    for (int i = 0; i < w.size(); i++)
    {
        if (often.count(w[i]))
        {
            often[w[i]]++;
        }
        else
        {
            often[w[i]] = 1;
        }
    }

    for (auto iter = often.begin(); iter != often.end(); iter++)
    {
        if (iter->second % 2 != 0)
        {
            cout << "No" << endl;
            return (0);
        }
    }
    cout << "Yes" << endl;
    return (0);
}

Measured memory_bytes: 256
import math

class Vector:
    def __init__(self,x,y):
        self.x = x
        self.y = y
        
    def __add__(self,other):
        return Vector(self.x+other.x,self.y+other.y)
    
    def __sub__(self,other):
        return Vector(self.x-other.x,self.y-other.y)
    
    def __mul__(self,scalar):
        return Vector(self.x*scalar,self.y*scalar)
    def __rmul__(self, scalar):
        return Vector(self.x*scalar,self.y*scalar)
   
    def __repr__(self):
        return str([self.x,self.y])
        
    def norm_2(self):
        return dot(self,self)
    
    def norm(self):
        return math.sqrt(self.norm_2())
    
def v_sum(v1,v2):
    return Vector(v1.x+v2.x,v1.y+v2.y) 
def scalar_multi(k,v):
    return Vector(k*v.x,k*v.y)
def v_diff(v1,v2):
    return v_sum(v1,scalar_multi(-1,v2))
    
def dot(vector1,vector2):
    return vector1.x*vector2.x+vector1.y*vector2.y

def cross(vector1,vector2):
    return vector1.x*vector2.y-vector1.y*vector2.x
    
    
    
q = int(input())
for i in range(q):
    x1,y1,x2,y2,x3,y3,x4,y4 = map(float,input().split())
    p1 = Vector(x1,y1)
    p2 = Vector(x2,y2)
    p3 = Vector(x3,y3)
    p4 = Vector(x4,y4)
    
    k = cross(p2-p4,p3-p4)/cross(p3-p4,p1-p2)
    ans = k*(p1-p2)+p2
    
    print("{} {}".format(ans.x,ans.y))


Measured memory_bytes: 5704
#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
const int N=1e5;
int n,s,pos[N+1];
long long arr[N+1];
template<class T>T read()
{
	T ret=0;
	char c=getchar();
	while(!isdigit(c)) {
		c=getchar();
	}
	while(isdigit(c)) {
		ret=ret*10+c-'0';
		c=getchar();
	}
	return ret;
}
long long solve(int fro,int to,int end)
{
	if(s<=pos[fro]) {
		return pos[to]-s;
	}
	if(s>=pos[to]) {
		return s-pos[fro];
	}
	if(arr[fro]>=arr[to]) {
		arr[fro]+=arr[to];
		return solve(fro,to-1,fro)+(end==to?pos[to]-pos[fro]:0);
	} else {
		arr[to]+=arr[fro];
		return solve(fro+1,to,to)+(end==fro?pos[to]-pos[fro]:0);
	}
}
int main()
{
	n=read<int>(),s=read<int>();
	for(int i=1;i<=n;++i) {
		pos[i]=read<int>(),arr[i]=read<long long>();
	}
	printf("%lld\n",solve(1,n,arr[1]<arr[n]?1:n));
	return 0;
}


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

#define vec                vector<int>
#define vecll              vector<ll>
#define vecst              vector<string>
#define vecb               vector<bool>
#define vec2(var, n, m)    vector<vector<int>> var(n, vector<int>(m, 0))
#define vecll2(var, n, m)  vector<vector<ll>> var(n, vector<ll>(m, 0))

#define rep(i,n)         for(ll i=(ll)0; i<(ll)n; i++)
#define REP(i,m,n)       for(ll i=(ll)m; i<(ll)n; i++)
#define arr(var, n)      vec var(n); rep(i,n){cin >> var[i];}
#define arrll(var, n)    vecll var(n); rep(i,n){cin >> var[i];}
#define arrst(var, n)    vecst var(n); rep(i,n){cin >> var[i];}
#define all(var)         (var).begin(), (var).end()
#define sortall(var)     sort(all(var))
#define uniqueall(v)     v.erase(unique(v.begin(), v.end()), v.end());
#define f_sum(var)       accumulate(all(var), 0)
#define f_sumll(var)     accumulate(all(var), 0LL)
#define chmin(v1, v2)    v1 = min(v1, v2)
#define chmax(v1, v2)    v1 = max(v1, v2)
#define mp(v1, v2)       make_pair(v1, v2)
#define pb(var)          push_back(var)
#define prt(var)         cout << (var) << "\n"
#define prtd(n, var)     cout << fixed << setprecision(n) << var << "\n"
#define prtfill(n, var)  cout << setw(n) << setfill('0') << var;
#define prt2(v1, v2)     cout << v1 << " " << v2 << "\n"
#define prt3(v1, v2, v3) cout << v1 << " " << v2 << " " << v3 << "\n"
#define prtall(v)        rep(i,v.size()){cout<<v[i]<<(i!=v.size()-1?" ":"\n");}
void prtok(bool ok){prt(ok ? "YES" : "NO");}
//----------------------------------------------------------------

int main(void) {
  int h, w;
  cin >> h >> w;
  arrst(s,h);

  rep(i,w+2){
    cout << '#';
  }
  cout << "\n";
  rep(i,h){
    cout << ('#'+s[i]+'#') << "\n";
  }
  rep(i,w+2){
    cout << '#';
  }
  cout << "\n";
}


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

using namespace std;

int field[20][20];
int dp[2][1 << 20];

int main(){
	int N;
	cin >> N;
	for(int caseNum = 1; caseNum <= N; ++caseNum){
		int H, W;
		cin >> W >> H;
		memset(field, 0, sizeof(field));
		memset(dp, 0, sizeof(dp));
		for(int i = 0; i < H; ++i){
			for(int j = 0; j < W; ++j){ cin >> field[i][j]; }
		}
		int all_mask = (1 << W) - 1;
		int top_mask = (1 << (W - 1));
		int left_mask = 1;
		int answer = 0;
		for(int i = 0; i <= W * H; ++i){
			int cur = (i & 1), next = 1 - cur;
			int x = field[i / W][i % W];
			bool leftmost = (i % W == 0);
			for(int j = 0; j < (1 << W); ++j){
				answer = max(answer, dp[cur][j]);
				int nbit = (j << 1) & all_mask;
				dp[next][nbit] = max(dp[next][nbit], dp[cur][j]);
				if(!(j & top_mask) && (leftmost || !(j & left_mask))){
					nbit |= 1;
					dp[next][nbit] = max(dp[next][nbit], dp[cur][j] + x);
				}
				dp[cur][j] = 0;
			}
		}
		cout << "Case " << caseNum << ": " << answer << endl;
	}
	return 0;
}

Measured memory_bytes: 9060
h, w = map(int, input().split())
mp = []
for i in range(10):
    mp.append(list(map(int, input().split())))
wall = []
for i in range(h):
    wall.append(list(map(int, input().split())))

min_mp = mp[:][:]
for i in range(10):
    for j in range(10):
        for k in range(10):
            mp[j][k] = min(mp[j][k], mp[j][i] + mp[i][k])

ans = 0
for i in range(h):
    for n in wall[i]:
        if n != -1 and n != 1:
            ans += min_mp[n][1]

print(ans)


Measured memory_bytes: 3444
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>

#define rep(i, m, n) for(int i=int(m);i<int(n);i++)
#define all(c) begin(c),end(c)

template<typename T1, typename T2>
inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }

template<typename T1, typename T2>
inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }

//改造
typedef long long int ll;
using namespace std;
#define INF (1 << 30) - 1
#define INFl (ll)5e15
#define DEBUG 0 //デバッグする時1にしてね
#define dump(x)  cerr << #x << " = " << (x) << endl
#define MOD 1000000007


//ここから編集する

typedef string::const_iterator State;

int expression(State &begin);

int term(State &begin);

int factor(State &begin);

int number(State &begin);

int expression(State &begin) {
    int ret = term(begin);
    while (true) {
        if (*begin == '+') {
            begin++;
            ret += term(begin);
        } else if (*begin == '-') {
            begin++;
            ret -= term(begin);
        } else {
            break;
        }
    }
    return ret;
}

int term(State &begin) {
    int ret = factor(begin);
    while (true) {
        if (*begin == '*') {
            begin++;
            ret *= factor(begin);
        } else if (*begin == '/') {
            begin++;
            ret /= factor(begin);
        } else {
            break;
        }
    }
    return ret;
}

int factor(State &begin) {
    if (*begin == '(') {
        begin++;
        int ret = expression(begin);
        begin++;
        return ret;
    }
    return number(begin);
}

int number(State &begin) {
    int ret = 0;
    while (isdigit(*begin)) {
        ret *= 10;
        ret += *begin - '0';
        begin++;
    }
    return ret;
}

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

    int N;
    cin >> N;
    cin.ignore();
    while (N--) {
        string s;
        getline(cin, s);
//        cin.ignore();
        State begin = s.begin();
        int ans = expression(begin);
        cout << ans << endl;
    }


    return 0;
}



Measured memory_bytes: 3140
#include <iostream>
#include <cstdio>

using namespace std;

int W, H;

int field[52][52];
bool visited[52][52];
int tx[] = {1, 1, 1, 0, -1, -1, -1, 0};
int ty[] = {1, 0, -1, -1, -1, 0, 1, 1};

void island(int y, int x)
{
  visited[y][x] = true;
  for (int i = 0; i < 8; i++) {
    if (!visited[y + ty[i]][x + tx[i]] && field[y + ty[i]][x + tx[i]] == 1) {
      island(y + ty[i], x + tx[i]);
    }
  }
}

void solve()
{
  fill_n(&visited[0][0], 52 * 52, false);
  int c = 0;
  for (int i = 1; i <= H; i++) {
    for (int j = 1; j <= W; j++) {
      if (!visited[i][j] && field[i][j] == 1) {
	island(i, j);
	c++;
      }
    }
  }
  printf("%d\n", c);
}

int main()
{
  while (scanf("%d %d ", &W, &H) == 2) {
    if (W == 0 && H == 0) {
      return 0;
    }
    fill_n(&field[0][0], 52 * 52, 0);
    for (int i = 1; i <= H; i++) {
      for (int j = 1; j <= W; j++) {
	scanf("%d ", &field[i][j]);
      }
    }
    solve();
  }
}

Measured memory_bytes: 0
#include<iostream>
#include<map>
#include<algorithm>
using namespace std;
#define endl "\n"
const int N = 1e6 + 5;
#define ll long long
ll a[N];

int main()
{
	ios_base::sync_with_stdio (false);
    cin.tie (NULL);
    ll n,i;
    cin>>n;
    for(i=0;i<n;i++)
    	cin>>a[i];
    ll xorans=a[0];
    for(i=1;i<n;i++)
       xorans=a[i]^xorans;
   //cout<<xorans;
   for(i=0;i<n;i++)
   	a[i]=a[i]^xorans;
   
   for( i=0;i<n;i++)
   	cout<<a[i]<<' ';

   return 0;
}

Measured memory_bytes: 5168
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <string>
#include <map>
#include <set>
#include <locale.h>
#include <vector>
#include <iomanip>
#include <cassert>
#include <cstring>

#define all(x) x.begin(), x.end()
#define sz(x) (int)(x.size())
#define pb push_back
#define mp make_pair
#define endl "\n"
#define rep(i,x,y) for(int i = x; i <= y; ++i)
#define repr(i,x,y) for(int i = x; i >= y; --i)
#define y1 wearsdfasdf
#define fi first
#define se second

typedef long long ll;

const int N = (int)(5e5) + 322;
const ll INF = (ll)(1e9) + 7;
const double eps = (1e-9);

using namespace std;


int main () {
  int a, b;
  cin >> a >> b;
  cout << __gcd(a, b) << endl;
  return 0;
}

Measured memory_bytes: 3088
#include<cstring>
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
using namespace std;
const long long Maxn=1e6;
typedef long long ll;

char s[Maxn];

int main(){
	int a,b;
	cin>>a>>b;
	int ans=0;
	for(int i=a;i<=b;i++){
		sprintf(s,"%d",i);
				if(s[0]==s[4]&&s[3]==s[1]){
					ans++;
				}
	}
	printf("%d\n",ans);
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
	"strings"
)

type bufReader struct {
	r   *bufio.Reader
	buf []byte
	i   int
}

var reader = &bufReader{
	bufio.NewReader(os.Stdin),
	make([]byte, 0),
	0,
}

func (r *bufReader) readLine() {
	if r.i < len(r.buf) {
		return
	}
	r.buf = make([]byte, 0)
	r.i = 0
	for {
		line, isPrefix, err := r.r.ReadLine()
		if err != nil {
			panic(err)
		}
		r.buf = append(r.buf, line...)
		if !isPrefix {
			break
		}
	}
}

func (r *bufReader) next() string {
	r.readLine()
	from := r.i
	for ; r.i < len(r.buf); r.i++ {
		if r.buf[r.i] == ' ' {
			break
		}
	}
	s := string(r.buf[from:r.i])
	r.i++
	return s
}

func (r *bufReader) nextLine() string {
	r.readLine()
	s := string(r.buf[r.i:])
	r.i = len(r.buf)
	return s
}

var writer = bufio.NewWriter(os.Stdout)

func next() string {
	return reader.next()
}

func nextInt64() int64 {
	i, err := strconv.ParseInt(reader.next(), 10, 64)
	if err != nil {
		panic(err)
	}
	return i
}

func nextInt() int {
	return int(nextInt64())
}

func nextLine() string {
	return reader.nextLine()
}

func out(a ...interface{}) {
	fmt.Fprintln(writer, a...)
}

func max64(x, y int64) int64 {
	if x > y {
		return x
	}
	return y
}

func max(x, y int) int {
	return int(max64(int64(x), int64(y)))
}

func min64(x, y int64) int64 {
	if x < y {
		return x
	}
	return y
}

func min(x, y int) int {
	return int(min64(int64(x), int64(y)))
}

func abs64(x int64) int64 {
	if x < 0 {
		return -x
	}
	return x
}

func abs(x int) int {
	return int(abs64(int64(x)))
}

func joinInt64s(a []int64, sep string) string {
	b := make([]string, len(a))
	for i, v := range a {
		b[i] = strconv.FormatInt(v, 10)
	}
	return strings.Join(b, sep)
}

func joinInts(a []int, sep string) string {
	b := make([]string, len(a))
	for i, v := range a {
		b[i] = strconv.Itoa(v)
	}
	return strings.Join(b, sep)
}

func divUp64(x, y int64) int64 {
	return (x + y - 1) / y
}

func divUp(x, y int) int {
	return int(divUp64(int64(x), int64(y)))
}

func gcd64(x, y int64) int64 {
	if x < y {
		x, y = y, x
	}
	for y != 0 {
		x, y = y, x%y
	}
	return x
}

func gcd(x, y int) int {
	return int(gcd64(int64(x), int64(y)))
}

func lcm64(x, y int64) int64 {
	return x * y / gcd64(x, y)
}

func lcm(x, y int) int {
	return int(lcm64(int64(x), int64(y)))
}

func pow64(x, y int64) int64 {
	return int64(math.Pow(float64(x), float64(y)))
}

func pow(x, y int) int {
	return int(pow64(int64(x), int64(y)))
}

func main() {
	solve()
	writer.Flush()
}

func solve() {
	n := nextInt()
	ma, mi := 0, 0
	for i := 0; i < n; i++ {
		a := nextInt()
		if i == 0 {
			ma = a
			mi = a
		} else {
			ma = max(ma, a)
			mi = min(mi, a)
		}
	}
	out(ma - mi)
}


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

typedef struct pp {
  char name[100];
  int time;
} P;

int head,tail,n;
P Q[LEN];

void enqueue(P x) {
  Q[tail] = x;
  tail = (tail + 1) % LEN;
}

P dequeue() {
  P x = Q[head];
  head = (head + 1) % LEN;
  return x;
}

int min(int a, int b) {
  return a < b ? a : b;
}


int main() {

int elaps = 0,q,c;
P u;
cin >> n >> q;

for(int i = 1; i <= n; i++) {
  cin >> Q[i].name >> Q[i].time;
}

head = 1;
tail = n + 1;

while(head != tail) {
  u = dequeue();
  c = min(u.time,q);
  u.time -= c;
  elaps += c;
  if(u.time > 0) {
    enqueue(u);
  }else {
    cout << u.name << " " << elaps << endl;
  }
}

}


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
using P = pair<ll, ll>;
using V = vector<ll>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep1(i, n) for(ll i=1;i<=(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
#define ALL(obj) (obj).begin(), (obj).end()
#define MOD 1000000007
#define INF 1000000000

// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 1000000007;
struct mint {
	ll x; // typedef long long ll;
	mint(ll x = 0) :x((x% mod + mod) % mod) {}
	mint operator-() const { return mint(-x); }
	mint& operator+=(const mint a) {
		if ((x += a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator-=(const mint a) {
		if ((x += mod - a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator*=(const mint a) {
		(x *= a.x) %= mod;
		return *this;
	}
	mint operator+(const mint a) const {
		mint res(*this);
		return res += a;
	}
	mint operator-(const mint a) const {
		mint res(*this);
		return res -= a;
	}
	mint operator*(const mint a) const {
		mint res(*this);
		return res *= a;
	}
	mint pow(ll t) const {
		if (!t) return 1;
		mint a = pow(t >> 1);
		a *= a;
		if (t & 1) a *= *this;
		return a;
	}

	// for prime mod
	mint inv() const {
		return pow(mod - 2);
	}
	mint& operator/=(const mint a) {
		return (*this) *= a.inv();
	}
	mint operator/(const mint a) const {
		mint res(*this);
		return res /= a;
	}
};

// nCr
// combination mod prime
// https://www.youtube.com/watch?v=8uowVvQ_-Mo&feature=youtu.be&t=1619
// usage:
//   combination comb(n+5);
//   ans = comb(n,r);
struct combination {
	vector<mint> fact, ifact;
	combination(int n) :fact(n + 1), ifact(n + 1) {
		assert(n < mod);
		fact[0] = 1;
		for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i;
		ifact[n] = fact[n].inv();
		for (int i = n; i >= 1; --i) ifact[i - 1] = ifact[i] * i;
	}
	mint operator()(int n, int k) {
		if (k < 0 || k > n) return 0;
		return fact[n] * ifact[k] * ifact[n - k];
	}
};

void solve_abc094() {
	ll n;
	cin >> n;

	V a(n);
	rep(i, n) {
		cin >> a[i];
		a[i] *= 2;
	}

	sort(ALL(a));

	ll ans1, ans2;

	ans1 = a[n-1] / 2;
	auto itr = lower_bound(ALL(a), ans1);

	ll num;
	num = (ll)(itr - a.begin());

	if (num > 0) {
		if (num == n) {
			ans2 = a[num - 1] / 2;
		}
		else
		{
			if (abs(a[num] - ans1) < abs(a[num - 1] - ans1)) {
				ans2 = a[num] / 2;
			}
			else {
				ans2 = a[num - 1] / 2;
			}
		}
	}
	else {
		ans2 = a[num] / 2;
	}

	cout << ans1 << " " << ans2 << "\n";
}

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

	solve_abc094();

	return 0;
}

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

int main(){

  int n;
  while( cin >> n, n ) {
    int k[101];
    for(int i=0; i<n; i++) {
      cin >> k[i];
    }
    string s;
    cin >> s;
  
    int now = 0;
    for(int i=0; i<s.size(); i++) {
      int num = k[now];
      for(int j=0; j<k[now]; j++) {
	s[i]--;
	if( s[i] == 'a'-1 ) {
	  s[i] = 'Z';
	}
	if( s[i] == 'A'-1 ) {
	  s[i] = 'z';
	}
      }
      now++;
      if( now == n ) {
	now = 0;
      }
    }
    
    cout << s << endl;
  }
}

Measured memory_bytes: 1208
n=int(input())
c=input()

r=0
w=0

for i in range(n):
    if c[i]=="R":
        r+=1
    else:
        w+=1

delete=0

for j in range(r):
    if c[j]=="W":
        delete+=1

if r>=delete:
    print(delete)
else:
    print(delete + (r-delete))

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

int solve(int n, const vector<vector<int> > & g) {
    vector<vector<int> > h(n);
    function<int (int, int, int)> go = [&](int i, int parent, int ancestor) {
        if (g[i].size() == 1) {
            return -1;
        } else if (g[i].size() == 2) {
            for (int j : g[i]) if (j != parent) {
                return go(j, i, ancestor);
            }
            assert (false);
        } else {
            if (ancestor != -1) {
                h[i].push_back(ancestor);
            }
            for (int j : g[i]) if (j != parent) {
                int k = go(j, i, i);
                if (k != -1) {
                    h[i].push_back(k);
                }
            }
            return i;
        }
    };

    assert (n >= 2);
    int root = 0;
    while (root < n and g[root].size() < 3) {
        ++ root;
    }
    if (root == n) {
        return 1;
    }
    go(root, -1, -1);

    int cnt = 0;
    REP (i, n) if (g[i].size() >= 3) {
        cnt += max(0, (int)g[i].size() - (int)h[i].size() - 1);
    }
    return cnt;
}

int main() {
    // input
    int n; cin >> n;
    vector<vector<int> > g(n);
    REP (i, n - 1) {
        int a, b; cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    // solve
    int answer = solve(n, g);

    // output
    cout << answer << endl;
    return 0;
}


Measured memory_bytes: 13440
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define get_unique(x) x.erase(unique(all(x)), x.end());
typedef long long ll;
typedef complex<double> Complex;
const int INF = 1e9;
const ll MOD = 1e9 + 7;
const ll LINF = 1e18;
template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
int n;
vector<ll> a;
auto memo = make_vec<ll>(3030, 3030);
ll dp(int l, int r) {
    if (memo[l][r] != -1) return memo[l][r];
    int len = r - l + 1;
    if (len == 0) return 0;
    ll ret;
    if (len % 2 == n % 2) {
        if (len == 1)
            ret = a[l];
        else
            ret = max(dp(l + 1, r) + a[l], dp(l, r - 1) + a[r]);
    } else {
        if (len == 1)
            ret = -a[l];
        else
            ret = min(dp(l + 1, r) - a[l], dp(l, r - 1) - a[r]);
    }
    return memo[l][r] = ret;
}
int main() {
    cin >> n;
    a.resize(n);
    rep(i, n) cin >> a[i];
    rep(i, 3030) rep(j, 3030) memo[i][j] = -1;
    cout << dp(0, n - 1) << endl;
}

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

const int MAXN = 200005;

int N, a[MAXN];

int main(){
	scanf("%d", &N);
	
	stack < pair <int, int> > s;
	long long res = 0, cur = 0;
	
	for(int i = 0; i < N; i++){
		scanf("%d", &a[i]);
		
		int cnt = 1;
		while(!s.empty()){
			pair <int, int> t = s.top();
			if(t.first < a[i])break;
			
			s.pop();
			cur -= 1LL * t.first * t.second;
			cnt += t.second;
		}
		s.push(make_pair(a[i], cnt));
		cur += 1LL * a[i] * cnt;
		
		res += cur;
	}
	
	printf("%lld\n", res);
	
	return 0;
}


Measured memory_bytes: 2688
#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>

#include <limits.h>

using namespace std;

typedef long long ll;

template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

int main(void) {
    int N, K;
    cin >> N >> K;

    vector<int> ps(N);
    for (int i = 0; i < N; i++) {
        cin >> ps[i];
    }
    sort(ps.begin(), ps.end());

    int ans = 0;
    for (int i = 0; i < K; i++) {
        ans += ps[i];
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3628
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(1000000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]


def gcd(n, m):
    if n % m == 0:
        return m
    else:
        return gcd(m, n % m)


def gcd_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = gcd(v, L[i])

    return v


def lcm(n, m):
    return (n * m) // gcd(n, m)


def lcm_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = lcm(v, L[i])

    return v


# Width First Search (+ Distance)
def wfs_d(D, N, K):
    """
    D: 隣接行列(距離付き)
    N: ノード数
    K: 始点ノード
    """

    dfk = [-1] * (N + 1)
    dfk[K] = 0

    cps = [(K, 0)]
    r = [False] * (N + 1)
    r[K] = True
    while len(cps) != 0:
        n_cps = []
        for cp, cd in cps:
            for i, dfcp in enumerate(D[cp]):
                if dfcp != -1 and not r[i]:
                    dfk[i] = cd + dfcp
                    n_cps.append((i, cd + dfcp))
                    r[i] = True

        cps = n_cps[:]

    return dfk


# Depth First Search (+Distance)
def dfs_d(v, pre, dist):
    """
    v:  現在のノード
    pre: １つ前のノード
    dist: 現在の距離

    以下は別途用意する
    D: 隣接リスト(行列ではない)
    D_dfs_d: dfs_d関数で用いる，始点ノードから見た距離リスト
    """

    global D
    global D_dfs_d

    D_dfs_d[v] = dist

    for next_v, d in D[v]:
        if next_v != pre:
            dfs_d(next_v, v, dist + d)

    return


def sigma(N):
    ans = 0
    for i in range(1, N + 1):
        ans += i
    return ans


class Combination:
    def __init__(self, n, mod):

        g1 = [1, 1]
        g2 = [1, 1]
        inverse = [0, 1]
        for i in range(2, n + 1):
            g1.append((g1[-1] * i) % mod)
            inverse.append((-inverse[mod % i] * (mod // i)) % mod)
            g2.append((g2[-1] * inverse[-1]) % mod)
        self.MOD = mod
        self.N = n
        self.g1 = g1
        self.g2 = g2
        self.inverse = inverse

    def __call__(self, n, r):
        if (r < 0 or r > n):
            return 0
        r = min(r, n - r)
        return self.g1[n] * self.g2[r] * self.g2[n - r] % self.MOD


# --------------------------------------------

dp = None


def main():
    N = int(input())
    A = li_input()

    print(max(A) - min(A))


main()


Measured memory_bytes: 4720
#include <bits/stdc++.h>
#define ll long long int
#define pr pair<ll, ll>
#define tp tuple<ll, ll, ll>
using namespace std;
long long int mod = 1e9 + 7;

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

    ll n, m, x;
    cin >> n >> m >> x;
    ll c[n], a[n][m];
    for (ll i = 0; i < n; i++)
    {
        cin >> c[i];
        for (ll j = 0; j < m; j++)
            cin >> a[i][j];
    }
    ll ans = 1e16, val = pow(2, n);
    for (ll i = 0; i < val; i++)
    {
        ll temp = i, cost = 0, flag = 1, t[m];
        memset(t, 0, sizeof(t));
        for (ll j = 0; j < n; j++)
        {
            if (temp % 2 == 1)
            {
                cost += c[j];
                for (ll k = 0; k < m; k++)
                    t[k] += a[j][k];
            }
            temp /= 2;
        }
        for (ll j = 0; j < m; j++)
        {
            if (t[j] < x)
                flag = 0;
        }

        if (flag)
            ans = min(ans, cost);
    }
    if (ans == (ll)1e16)
        ans = -1;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4116
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#define ll long long
#define PI 3.141592653589
#define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define EPS 1e-7
#define PII pair<int,int>
#define s second
#define f first
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;
ll MOD = 998244353;
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int random_int(int l,int r){return uniform_int_distribution<int>(l,r)(rng);}
ll fast_power(ll x, ll p){
    ll res = 1;
    while(p > 0){
        if(p & 1){
            res = (res * x)%MOD;
        }
        p = p >> 1;
        x = (x*x)%MOD;
    }
    return res;
}
int main() {
    IO;
    int n, k;
    cin >> n >> k;
    int arr[n];
    for(int i = 0; i < n; i++){
        cin >> arr[i];
    }
    int dp[n];
    dp[0] = 0;
    for(int i = 1; i < n; i++){
        dp[i] = INT_MAX;
        for(int j = 1; j <= k; j++){
            if(i-j >= 0){
                dp[i] = min(dp[i], abs(arr[i]-arr[i-j]) + dp[i-j]);
            }
        }
    }
    cout << dp[n-1];

    return 0;
}


Measured memory_bytes: 1024
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    n = int(ipt())
    a = [[int(i) for i in ipt().split()] for _ in range(n)]

    for i in range(n):
        for j in range(n):
            for k in range(n):
                if a[j][k] > a[j][i]+a[i][k]:
                    print(-1)
                    exit()
    for i in range(n):
        for j in range(n):
            for k in range(n):
                if a[j][i] != 0 and a[i][k] != 0 and a[j][k] == a[j][i]+a[i][k]:
                    a[j][k] = 0

    ans = 0
    for i in range(n):
        for j in range(i,n):
            ans += a[i][j]

    print(ans)

    return None

if __name__ == '__main__':
    main()


Measured memory_bytes: 76832
#include<stdio.h>
int main()
{
    int h,n,y=0,i,z;
    scanf("%d",&h);
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%d",&z);
        y=y+z;
    }
    if(h<=y)

        printf("Yes");
    else
        printf("No");

}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M = 2e5+7;
const int mod =1e9+7;
ll pz[M],pf[M];
ll z[M],f[M];
int main()
{
	ios::sync_with_stdio(false);cin.tie(0);
  	int n;
	cin>>n;
	ll ans=0;
	for(int i=1;i<=n;i++)ans+=(ll)i*(n-i+1);
	for(int i=1;i<n;i++)
	{
		ll u,v;
		cin>>u>>v;
		if(u>v)swap(u,v);
		ans-=u*(n-v+1);
	 } 
	 cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3648
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;string a,b,c;cin>>n>>a>>b>>c;
    int ans = 0;
    for(int i=0;i<a.length();i++){
        set<char> m;m.insert({a[i],b[i],c[i]});
        ans += m.size()-1;
    }
    cout<<ans;
}

Measured memory_bytes: 256
#include<stdio.h>

main(void)
{
	int a[10],b,c,d;
	
	for(b=0;b<10;b++){
		scanf("%d",&a[b]);
	}
	for(b=0;b<10;b++){
		for(d=9;d>0;d--){
			if(a[d-1]>a[d]){
				c=a[d];
				a[d]=a[d-1];
				a[d-1]=c;
			}
		}
	}
	
	printf("%d\n%d\n%d\n",a[9],a[8],a[7]);
	
	return 0;
}

Measured memory_bytes: 600
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
int main()
{
    ios::sync_with_stdio(false);
    int t;
    cin >>t;
    for(int i=1;i<=t;i++)
        {
            ll a,b,c,d;
            cin >>a>>b>>c>>d;
            if(a<b){cout <<"No"<<endl;continue;}
            if(a>=b&&d>=b&&c>=b){cout <<"Yes"<<endl;continue;}
            if(d<b){cout <<"No"<<endl;continue;}
            if(c>=b)
                {
                    if(d<b){cout <<"No"<<endl;continue;}
                    else {cout <<"Yes"<<endl;continue;}
                }
            else 
                {
                    ll g=__gcd(b,d);
                    if(b-g+a%g>c)
                        {cout <<"No"<<endl;continue;}
                    else {cout <<"Yes"<<endl;continue;}                        
                }
        }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;
void command(string &str, string com)
{
    if(com=="print")
    {
        int a,b;
        cin>>a>>b;
        for(int i=a;i<=b;i++)
            cout<<str[i];
        cout<<endl;
    }

    if(com=="replace")
    {
        int a,b;
        string rep;
        cin>>a>>b>>rep;
        for(int i=a;i<=b;i++)
            str[i]=rep[i-a];
    }
    if(com=="reverse")
    {
        int a,b;
        string tmp="";
        cin>>a>>b;
        for(int i=b;i>=a;i--)
            tmp+=str[i];
        for(int j=a;j<=b;j++)
                str[j]=tmp[j-a];
    }
}
int main()
{
    string str,com;
    string rep;
    int start,end,num;
    cin>>str;
    cin>>num;
    for(int i=0;i<num;i++)
    {
        cin>>com;
        command(str,com);
    }
    return 0;
}


Measured memory_bytes: 3176
N = int(input())
A = list(map(int, input().split()))

count = 0
for i in range(N):
    if (A[i] % 2 == 0) and (A[i] % 3 != 0) and (A[i] % 5 != 0):
        count += 1

if count == 0:
    print("APPROVED")
else:
    print("DENIED")

Measured memory_bytes: 3060
import java.util.Scanner;
public class Main {
public static void main(String[]srgs) {
	Scanner scan=new Scanner(System.in);
	int a=scan.nextInt();
	int c=0;
	for(int i=1;;i++) {
		c+=i;
		if(c>=a) {
			System.out.println(i);
			break;
		}
	}
	scan.close();
	}
}

Measured memory_bytes: 25300
#include <cstdio>
#include <functional>
#include <algorithm>
#include <vector>
#include <limits>
#include <numeric>
#include <type_traits>
#include <iostream>
#include <queue>
#include <math.h>
#include <bits/stdc++.h>
#include <queue>
#include <map>

using namespace std;

#define INF (1ll<<60)
#define INFint (1<<30)
#define MOD 1000000007
#define BOUND 27182818284

typedef long long ll;
typedef long long int lli;
typedef pair<int,int> P;

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

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

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

// gcd
template<typename T>
T gcd(T a, T b){
    if(a==0)
        return b;
    return gcd(b%a,a);
}

// gcd array
int findGCD(int arr[], int n){
    int result = arr[0];
    for (int i=1; i < n; i++)
        result = gcd(arr[i], result);

    return result;
}

template<typename T>
T lcm( T m, T n ){
    // 引数に0がある場合は0を返す
    if ( ( 0 == m ) || ( 0 == n ) )
        return 0;

    return ((m/gcd(m, n)) * n); // lcm = m * n / gcd(m,n)
}

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


int dx[5]={1,0,-1,0};
int dy[5]={0,1,0,-1};
// v.front() = -BOUND;
// v.back() = BOUND;

int main(){
    ll N,M;
    ll dp[100000];
    int num[11]={0,2,5,5,4,5,6,3,7,6};
    cin >> N >> M;
    vector<int> a(M);
    Fill(dp, -(ll)BOUND);

    rep(i,M){
        cin >> a[i];
    }
    sort(a.begin(), a.end(), greater<int>());
    dp[0]=0;
    for(int i=1; i<=N; i++){
        for(int j=0; j<M; j++){
            if(i-num[a[j]]>=0 && dp[i-num[a[j]]]>=0)
                dp[i]=max(dp[i-num[a[j]]]+1,dp[i]);
        }
    }

    ll j=N;
    string ans="";
    while(j>0){
        for(int i=0; i<M; i++){
            if(j-num[a[i]]<0) continue;
            if(dp[j-num[a[i]]] == dp[j]-1){
                j-=num[a[i]];
                ans+='0'+a[i];
                break;
            }
        }
    }
    cout << ans <<endl;
    return 0;
}



Measured memory_bytes: 1024