akhauriyash/Code-Regression huggingface dataset:
using System;
using static System.Console;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Threading;

namespace Atcoder_Answer
{
    class Program
    {
        const Int32 mod = 1000000007;

        static void Main(string[] args)
        {
            int K = int.Parse(ReadLine());
            string S = ReadLine();

            if (S.Length > K)
            {
                WriteLine(S.Substring(0, Math.Min(K, S.Length)) + "...");
            }
            else WriteLine(S);

            return;
        }

        #region Functions
        public static decimal floor(float d) => Math.Floor((decimal)d);

        public static double nqrt(int n, int value)
        {
            if (n >= 0)
            {
                // 通常のn乗根
                return Math.Pow(n, 1.0 / (double)n);
            }
            else
            {
                if ((n % 2) != 0)
                {
                    // 奇数乗根の場合
                    return -Math.Pow(-n, 1.0 / (double)n);
                }
                else
                {
                    // 偶数乗根の場合
                    return double.NaN;
                }
            }
        }
        #endregion
    }

    public static class Extension
    {
        #region 拡張:bool
        #region キャスト関連
        public static int ToInt(this bool Bool)
        {
            if (Bool) return 1;
            else return 0;
        }

        public static string ToString(this bool Bool, string TrueStr, string FalseStr)
        {
            if (Bool) return TrueStr;
            else return FalseStr;
        }
        #endregion
        #endregion

        #region 拡張:int
        #region キャスト関連
        public static char ToAlphaBets(this int Base) => (char)Base;
        #endregion
        #endregion

        #region 拡張:char
        #region 変換関連
        public static char NextAlpha(this char Char) => (char)((Char) + 1); //次の文字を取得
        #endregion
        #endregion

        #region 拡張:int[]
        public static long Sum(this int[] Array)
        {
            int Ret = 0;
            for (int loop = 0; loop < Array.Length; loop++) Ret += Array[loop];
            return Ret;
        }
        #endregion

        #region 拡張: string
        public static string Multi(this string THIS, int Value)
        {
            string RetValue = "";

            for (int loop = 0; loop < Value; loop++) RetValue += THIS;

            return RetValue;
        }
        #endregion

        #region 拡張: List<string>
        public static string Sum(this List<string> THIS, string Split)
        {
            string RetValue = "";

            for (int loop = 0; loop < THIS.Count; loop++)
            {
                RetValue += THIS[loop];
            }

            return RetValue;
        }
        #endregion
    }
}


Measured memory_bytes: 17624
n=int(input())
a=list(map(int,input().split()))
num=0
for i in range(n):
  if i%2==0:
    num=num+a[i]
  else:
    num=num-a[i]
k=num
for i in range(n):
  print(k,end=" ")
  k=2*a[i]-k
  

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

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}

using ll=long long;
using R=long double;
const R EPS=1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r){return(r > EPS)-(r < -EPS);}
inline R sq(R x){return sqrt(max(x,0.0L));}

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

// Problem Specific Parameter:

int main(void){
	string a,b,c;
	cin >> a >> b >> c;
	cout << a[0] << b[0] << c[0] << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cmath>
#include <queue>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
const int INF = 1<<29;

int main() {
  const int coin[] = {500,100,50,10,5,1};
  vector<int> dp(1000,INF);
  dp[0] = 0;
  REP(i,1000)
    REP(k,6)
      if (i+coin[k] < 1000)
        dp[i+coin[k]] = min(dp[i+coin[k]], dp[i] + 1);
  int n;
  while(cin>>n,n) {
    cout << dp[1000-n] << endl;
  }
}

Measured memory_bytes: 0
package main

import (
  "fmt"
  _ "sort"
  _ "math"
)

func main() {
  var a,b int
  fmt.Scan(&a,&b)

  if b - a >= 2019 {
    fmt.Printf("0\n")
    return
  }

  r := 2019

  for i:=a; i<=b; i++ {
    for j:=i+1; j<=b; j++ {
      t := i*j % 2019
      if r > t {
        r = t
      }
    }
  }


  fmt.Printf("%d\n", r)
}


Measured memory_bytes: 512
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int W = sc.nextInt();
        int H = sc.nextInt();
        int x = sc.nextInt();
        int y = sc.nextInt();
        int r = sc.nextInt();
    
        if(x-r<0 || x+r>W || y-r<0 || y+r>H){
            System.out.println("No");
        }else{
            System.out.println("Yes");
        }
    }
}


Measured memory_bytes: 26396
// A.cpp : このファイルには 'main' 関数が含まれています。プログラム実行の開始と終了がそこで行われます。
//

#include <iostream>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;
int main()
{
    int n, x, t;

    cin >> n >> x >> t;

    int a = n / x;
    int b = n % x;

    if (b != 0)a++;

    cout << t * a << endl;

    return 0;
}


Measured memory_bytes: 3592
#include<iostream>
#include<cstdio>
using namespace std;
int n,m;
int x;
long long ans;
int w[50][50];
int main()
{
    cin>>n>>m;
    for (int i=0; i<=9; ++i)
        for (int j=0; j<=9; ++j)
            cin>>w[i][j];
    for (int k=0; k<=9; ++k)
        for (int i=0; i<=9; ++i)
            for (int j=0; j<=9; ++j)
                if (w[i][k]+w[k][j]<w[i][j])
                    w[i][j]=w[i][k]+w[k][j];
    for (int i=1; i<=n; ++i)
        for (int j=1; j<=m; ++j)
        {
            cin>>x;
            if (x>=0)
                ans+=w[x][1];
        }
    cout<<ans<<endl;
    return 0;
}


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


int main(){

int N,M;
cin>>N>>M;
bool safe[N+1]={};
for(int i=0;i<=N;i++){
    char c;
    cin>>c;
    if(c=='0')safe[i]=true;
}


int now=N;
vector<int>ans;
while(1){
    int id=M;
    while(!safe[max(now-id,0)] && id>0){
        id--;
    }
    if(id==0){
        cout<<"-1"<<endl;
        return 0;
    }
    if(now-id<0)id=now;
    now-=id;
    ans.emplace(ans.begin(),id);
    if(now==0)break;

}


for(auto p:ans){
    cout<<p<<" ";
}

 return 0;
}
/*
9 3
0001000100

1 3 2 3


5 4
011110

-1


6 6
0101010

6
*/

Measured memory_bytes: 1144
import sys, math
from collections import defaultdict
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

A, B, C = rl()

print(max(C-(A-B), 0))

Measured memory_bytes: 65180
#include <iostream>
using namespace std;
 
int main() {
    int L, R, d;
    int counter = 0;

    cin >> L >> R >> d;

    for (int i = L; i <= R; i++) {
        if (i % d == 0) {
            counter++;
        }
    }

    cout << counter << endl;
        
}

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

using namespace std;

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

    double a, b;
    cin >> a >> b;



    cout << std::setprecision(11) << a / b << endl;


    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<math.h>
#include<stdlib.h>
#include<string>
#include<iostream>
#include<set>
#include<map>
#include<deque>
using namespace std;
typedef long long ll;
typedef pair<ll, ll>pii;
typedef pair<pii, ll>pi3;
ll mod = 1000000007;
int main()
{
	int a, b, c;
	cin >> a >> b >> c;
	cout << min(min(a + b, b + c), c + a) << endl;
	//printf((a % 3 == 0 || b % 3 == 0 || (a + b) % 3 == 0) ? "Possible\n" : "Impossible\n");
}

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

int main(){
	
	char b; cin>>b;
	if(b=='A'||b=='T') cout<<(char)(b^'A'^'T')<<endl;
	else cout <<(char)(b^'G'^'C')<<endl;
}

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

#define ll long long
#define vl vector<ll>
#define vvl vector<vector<ll>> //vvl data(10, vector<ll>(10);
#define fo(i,a,b) for(ll i=a; i<b; i++)

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

    cout << a*b << endl;
}

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

int main()
{
    int n;
    cin>>n;
    int a[1001];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int ans1,ans2;
    for(int i=0;i<n;++i) for(int j=0;j<n;j++)
    {
        if(i==j) continue;
        if(abs(a[i]-a[j])%(n-1)==0)
        {
            ans1=a[i];
            ans2=a[j];
            break;
        }
    }
    cout << ans1 << " " << ans2 << endl;
    return 0;
}


Measured memory_bytes: 3088
#include <bits/stdc++.h>
using namespace std;
int main(){
    int q;
    cin >> q;
    vector<int> A;
    for(int i=0;i<q;i++){
        int num;
        cin >> num;
        if (num == 0){
            int x;
            cin >> x;
            A.push_back(x);
        }else if(num == 1){
            int p;
            cin >> p;
            cout << A[p] << endl;
        }else{
            A.pop_back();
        }
    }
}


Measured memory_bytes: 3812
import math

def func(x,y):
    x=math.pow(x,2)
    y=math.pow(y,2)
    s=math.sqrt((x+y))
    return s

if __name__=="__main__":
    li=list(map(int,input().split(" ")))
    n=li[0]
    d=li[1]
    count=0
    for _ in range(0,n):
        
        li=list(map(int,input().split(" ")))
        x=li[0]
        y=li[1]
        if(func(x,y) <=d):
            
            count+=1

    print(count)    

Measured memory_bytes: 9272
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Tarek
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        BMultiplication2 solver = new BMultiplication2();
        solver.solve(1, in, out);
        out.close();
    }

    static class BMultiplication2 {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt();
            long a[] = new long[n];
            int f = 0;
            long sum2 = (long) Math.pow(10, 18);
            for (int i = 0; i < n; i++) {
                a[i] = in.nextLong();
                if (a[i] == 0) f = 1;
            }
            if (f == 1) out.println("0");
            else {
                int m = 0;
                long sum = 1;
                for (int i = 0; i < n; i++) {
                    if ((sum * a[i]) > sum2) {
                        out.println("-1");
                        return;
                    }
                    if (1000000000000000000L / sum < a[i]) {
                        out.println("-1");
                        return;
                    } else {
                        sum = sum * a[i];
                    }
                }
                out.println(sum);
            }
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

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

    }
}



Measured memory_bytes: 50460
import java.util.*;

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

		int A = sc.nextInt();
		int B = sc.nextInt();
		boolean[] ans = new boolean[4];
		ans[A] = true;
		ans[B] = true;
		for (int i = 1; i < ans.length; i++) {
			if (!ans[i]) {
				System.out.println(i);
			}
		}
	}
}

Measured memory_bytes: 21844
module Main where
import qualified Control.Monad as C
import qualified Data.Char as C
import qualified Data.List as L
import qualified Data.Map as M
import qualified Data.Array as A

int = read :: String -> Int
getWord :: IO String
getWord = do
  c <- getChar
  if C.isSpace c
  then
    return []
  else do
    ws <- getWord
    return (c:ws)
getInt = fmap int getWord
replace pred a = map (\x -> if pred x then a else x)

main = interact $ printer . solver . parser
parser = map int . words
printer = unlines . (:[]) . show

solver (n:l:ss) = sum apples - a
  where
    apples = [l+i-1|i<-[1..n]]
    (m,a) = minimum $ zip (map abs apples) apples

Measured memory_bytes: 508
#include <iostream>
#include <algorithm>
#define INF (1 << 25)
using namespace std;

int main(){
  int cost[64][64];
  int n,a,b,c;
  while(cin >> n,n){
    int maxi = 0;
    fill_n(cost[0],64*64,INF);
    while(n--){
      cin >> a >> b >> c;
      cost[a][b] = cost[b][a] = c;
      cost[a][a] = cost[b][b] = 0;
      maxi = max(max(a,b),maxi);
    }
    for(int i=0;i<=maxi;i++){
      for(int j=0;j<=maxi;j++){
	for(int k=0;k<=maxi;k++){
	  cost[j][k] = min(cost[j][k],cost[j][i]+cost[i][k]);
	}
      }
    }
    int m_num,m_sum = INF;
    for(int i=0;i<=maxi;i++){
      int sum = 0;
      for(int j=0;j<=maxi;j++) sum += cost[i][j];
      if(m_sum > sum){
	m_sum = sum;
	m_num = i;
      }
    }
    cout << m_num << " " << m_sum << endl;
  }
}

Measured memory_bytes: 1176
import java.util.*;

public class Main {
	static class Diff {
		int index;
		int length;

		Diff(int index, int length) {
			this.index = index;
			this.length = length;
		}
	}

	int N, M;
	List<Integer> X;
	List<Diff> diffs;
	Comparator<Diff> comp = new Comparator<Diff>() {
		@Override
		public int compare(Diff o1, Diff o2) {
			if (o1.length < o2.length) {
				return 1;
			} else if (o1.length > o2.length) {
				return -1;
			} else {
				return 0;
			}
		}
	};

	void calcDiff() {
		diffs = new ArrayList<>(M - 1);
		for (int i = 0; i < M - 1; ++i) {
			diffs.add(new Diff(i, X.get(i + 1) - X.get(i)));
		}
		Collections.sort(diffs, comp);
	}

	long calc() {
		if (N >= M) {
			return 0;
		}
		long sum = X.get(X.size() - 1) - X.get(0);
		for (int i = 0; i < N - 1; ++i) {
			sum -= diffs.get(i).length;
		}
		return sum;
	}

	Main() {
		Scanner in = new Scanner(System.in);
		String[] tokens = in.nextLine().split(" ");
		N = Integer.parseInt(tokens[0]);
		M = Integer.parseInt(tokens[1]);
		X = new ArrayList<>(M);
		tokens = in.nextLine().split(" ");
		for (int i = 0; i < M; ++i) {
			X.add(Integer.parseInt(tokens[i]));
		}
		in.close();
		Collections.sort(X);
	}

	public static void main(String[] args) {
		Main ins = new Main();
		ins.calcDiff();
		System.out.println(ins.calc());
	}

}


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

using ll = long long;
using pii = pair<int, int>; using pll = pair<ll, ll>;

#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i < (n); i++)

template<class T> istream& operator >> (istream& s, vector<T>& v)
{ for (T& x: v) { s >> x; } return s;}
template<class F, class S> istream& operator >> (istream& s, pair<F, S>& p)
{ s >> p.first >> p.second; return s;}

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

    int ans = N + N * N + N * N * N;

    cout << ans << endl;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define endl '\n'
#define pb push_back
#define fi first
#define se second
#define PI acos(-1)
#define all(c) (c).begin(),(c).end()
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define TRACE
#ifndef ONLINE_JUDGE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	cerr << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

int modpow(int x, int n, int m) {
	x %= m;
	int res = 1;
	while(n > 0) {
		if(n & 1)
			res = res * x % m;
		x = x * x % m;
		n >>= 1;
	}
	return res;
}

const ll inf = 2e18;
const int mod = 1e9 + 7;
const int N = 1e5 + 10;

signed main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	srand(chrono::steady_clock::now().time_since_epoch().count());
	#ifndef ONLINE_JUDGE
		// freopen("input.txt", "r", stdin);
		// freopen("output.txt", "w", stdout);
	#endif

	int n;
	cin >> n;
	vector<pii> v;
	for(int i = 0; i < n; i++) {
		int x, l;
		cin >> x >> l;
		v.pb({x + l, x - l});
	}
	sort(all(v));
	int ans = 1, mx = v[0].fi;
	for(int i = 1; i < v.size(); i++) {
		if(v[i].se >= mx) {
			ans++;
			mx = v[i].fi;
		}
	}
	cout << ans;

	return 0;
}

Measured memory_bytes: 2420
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define de cout<<"debuglandınız\n";
#define N 1048576

set<ll int>sett;
set<ll int> :: iterator itr;

ll int n,k,t,mx,x,flag,b[1000005],a[1000005],i;
ll int c[1000005],d[1000005];
ll int vt1[N+N],vt2[N+N];

ll int bs(ll int sayi){
	ll int l=1,r=sett.size();
	while(l!=r){
		if(a[(l+r)/2]<sayi){
			l=(l+r)/2+1;
		}
		else{
			r=(l+r)/2;
		}
	}
	return l;
}

void update(ll int x){
	ll int a=bs(x);
	x=a+N-1;
	while(x){
		vt1[x]++;
		vt2[x]++;
		x/=2;
	}
	return;
}

ll int toplam(ll int node, ll int list, ll int rist, ll int l, ll int r){
	if(rist<l or list>r)return 0;
	if(l>=list and r<=rist){
		//return vt[node];
	}
	return toplam(node*2,list,rist,l,(l+r)/2) + toplam(node*2+1,list,rist,(l+r)/2+1,r);
}

int main(){
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	//cin>>n;
	int p,o,y;
	cin>>p>>o>>y;
	cout<<min(p+o,min(p+y,o+y));
	for(i=1;i<=n;i++){
		cin>>b[i];
		sett.insert(b[i]);
	}
	i=1;
	for(itr=sett.begin();itr!=sett.end();itr++){
		a[i]=*itr;
		i++;
	}
}

Measured memory_bytes: 2304
function main()
	N,X,Y,Z=map(x->parse(Int,x),split(readline()))
	A=Int[X,Y,Z]
	s=readlines()
	ans=Char[]
	for i=1:N
		id=Int[]
		for k=1:3
			if Char(k+64) in s[i]
				push!(id,k)
			end
		end
		if A[id[1]]!=A[id[2]]
			if A[id[1]]>A[id[2]]
				A[id[1]]-=1
				A[id[2]]+=1
				push!(ans,Char(id[2]+64))
			else
				A[id[1]]+=1
				A[id[2]]-=1
				push!(ans,Char(id[1]+64))
			end
		else
			if A[id[1]]==A[id[2]]==0
				println("No")
				exit()
			end
			if i<N&&Char(id[1]+64) in s[i+1]
				A[id[1]]+=1
				A[id[2]]-=1
				push!(ans,Char(id[1]+64))
			else
				A[id[1]]-=1
				A[id[2]]+=1
				push!(ans,Char(id[2]+64))
			end
		end
	end
	println("Yes")
	println.(ans)
end
main()


Measured memory_bytes: 209144
#include <iostream>
#include <vector>
using namespace std;
typedef long long int ll;
struct BIT{
    vector<int> bit;
    int size;
    BIT(int n):size(n), bit(n+1, 0){}
    int sum(int i){
        int s=0;
        while(i>0){
            s+=bit[i];
            i-=(i&(-i));
        }
        return s;
    }
    void add(int i, int x){
        while(i<=size){
            bit[i]+=x;
            i+=(i&(-i));
        }
    }
};
int main()
{
    int n;
    cin>>n;
    ll m=(ll)n*(ll)(n+1)/2;
    int a[100000];
    for(int i=0; i<n; i++){
        cin>>a[i];
    }
    int x1=0, x2=1e9+1;
    while(x1!=x2){
        int x=(x1+x2+1)/2;
        int s[100001];
        s[0]=0;
        for(int i=0; i<n; i++){
            if(a[i]>=x) s[i+1]=s[i]+1;
            else s[i+1]=s[i]-1;
        }
        BIT bit(2*n+1);
        ll ct=0;
        for(int i=0; i<=n; i++){
            ct+=(ll)bit.sum(n+1+s[i]);
            bit.add(n+1+s[i], 1);
        }
        if(ct>=(m+1)/2) x1=x;
        else x2=x-1;
    }
    cout<<x1<<endl;
    return 0;
}

Measured memory_bytes: 1804
#include<bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(0)
#define loop(i, a, b) for(lli i=a; i<b; i++)
#define loopb(i, a, b) for(lli i=a; i>=b; i--)
#define pb push_back
#define umap unordered_map
typedef long long int lli;
typedef pair<lli, lli> pii;
typedef vector<lli> vll;
typedef tree<lli, null_type, less<lli>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
// use to avoid collision
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
// for pair in unordered_map
struct hash_pair {
    template <class T1, class T2>
    size_t operator()(const pair<T1, T2>& p) const
    {
        auto hash1 = hash<T1>{}(p.first);
        auto hash2 = hash<T2>{}(p.second);
        return hash1 ^ hash2;
    }
};
lli power(lli x, lli y){
    lli res = 1;
    x = x ;
    while (y > 0) {
        if (y & 1)
            res = (res*x) ;
        y = y>>1;
        x = (x*x);
    }
    return res;
}
bool kmp(string& s, string& st){
	lli n = s.length();
	lli m = st.length();
	lli i = 0;
	lli j = 0;
	while(i < n && j < m){
		if(s[i] == st[j]){
			i++;
			j++;
			if(j == 3){
				return true;
			}
		}
		else
			i++;
	}
	return false;
}
lli solve(){
	lli n;
	string s;
	cin>>n>>s;
	lli count = 0;
	loop(i, 0, 10){
		loop(j, 0, 10){
			loop(k, 0, 10){
				string st = to_string(i) + to_string(j) + to_string(k);	
				if(kmp(s, st))
					count++;
			}
		}
	}
	cout<<count<<"\n";
	return 0;
}
int main(){
	fastio;
	lli t;
//	cin>>t;
	t = 1;
	while(t>0){
		t--;
		solve();
	}
}


Measured memory_bytes: 384
#include"bits/stdc++.h"
using namespace std;
unsigned long long dp[1001][1001],minx=999999999;
int main(){
	int n,m,d[1001],c[1001];
	cin>>n>>m;
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=n;i++){
		cin>>d[i];
	}
	for(int i=1;i<=m;i++){
		cin>>c[i];
	}
	for(int i=0;i<n;i++){
		for(int j=1+i;j<=m;j++){
			if(dp[i+1][j+1]==0){
				dp[i+1][j+1]+=dp[i][j]+c[j]*d[i+1];
			}
			if(dp[i][j]!=0&&dp[i][j]<dp[i][j+1]){
				dp[i][j+1]=dp[i][j];
			}
		}
	}
	for(int i=m-n+1;i<=m+1;i++){
		if(dp[n][i]<minx&&dp[n][i]!=0)minx=min(dp[n][i],minx);
	}
	cout<<minx<<endl;
}

Measured memory_bytes: 10928
#include <iostream>
#include <algorithm>
#include <vector>
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
using namespace std;
int n;
int main()
{
  cin >> n;
  cout << n*n*n << "\n";
  return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
 
const ll INF = 1e18;

int n;
ll a[405], sum[405];
ll dp[405][405];

ll dfs(int l, int r){
    if(l == r) return 0;
    if(dp[l][r] != INF) return dp[l][r];
    ll cost = sum[r+1] - sum[l];
    ll res = INF;
    for(int k = l; k < r; k++){
        chmin(res, dfs(l,k) + dfs(k+1,r) + cost);
    }
    return dp[l][r] = res;
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
    cin >> n;
    rep(i,n){
        cin >> a[i];
        sum[i+1] = a[i] + sum[i];
    }
    rep(i,n)rep(j,n) dp[i][j] = INF;
    ll ans = dfs(0, n-1);
    cout << ans << endl;
	return 0;
}

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

const int maxn=1e5+7;
int da[maxn],db[maxn],dc[maxn],d[maxn<<2];
int x,y,a,b,c;
long long ans;

bool cmp(int a,int b)
{
	return a>b;
}

int main()
{
	scanf("%d %d %d %d %d",&x,&y,&a,&b,&c);
	for(int i=1;i<=a;++i) scanf("%d",&da[i]);
	for(int i=1;i<=b;++i) scanf("%d",&db[i]);
	for(int i=1;i<=c;++i) scanf("%d",&dc[i]);
	for(int i=1;i<=a;++i) d[i]=da[i];
	for(int i=1;i<=b;++i) d[i+a]=db[i];
	sort(da+1,da+a+1,cmp);
	sort(db+1,db+b+1,cmp);
	for(int i=1;i<=x;++i) d[i]=da[i];
	for(int i=1;i<=y;++i) d[i+x]=db[i];
	for(int i=1;i<=c;++i) d[i+x+y]=dc[i];
	sort(d+1,d+x+y+c+1,cmp);
	for(int i=1;i<=x+y;++i) ans+=d[i];
	printf("%lld",ans);
}

Measured memory_bytes: 2560
/*
    author : Divyansh Gupta
    email : divyanshg10@gmail.com
*/

#include <iostream>
#include <iomanip>
#include <cstring>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <utility>
#include <map>

using namespace std;

#define test_case int test_cases;\
                cin>>test_cases;\
                while(test_cases--)
#define loopup(var,l,r) for(var=l;var<r;var++)
#define loopdown(var,r,l) for(var=r;var>=l;var--)
#define ll long long
#define mp make_pair
#define pb push_back
#define vi vector<int>
#define pii pair<int,int>                   
#define br cout<<"\n"
#define sp cout<<" "
#define pr cout<<
#define mod 1000000007

vector<vector<double> > dp(3000,vector<double>(3000,-1));

double prob(int n,vector<double> &P,int x) {
    // pr dp[n][x];br;
    if(x == 0)
        return 1.0;
    if(n == 0) 
        return 0.0;
    if(dp[n][x] != -1) {
        return dp[n][x];
    }
    dp[n][x] = P[n] * prob(n-1,P,x-1) + (1 - P[n]) * prob(n-1,P,x);
    return dp[n][x];
}

void solve(){
	int n,i,j;
    double x;
    cin>>n;
    vector<double> P;
    P.pb(0);
    loopup(i,1,n+1) {
        cin>>x;
        P.pb(x);
    }
    loopup(i,0,n+1) {
        loopup(j,0,n+1) {
            dp[i][j] = -1;
        }
    }
    cout<<setprecision(10)<<prob(n,P,(n+1)/2);
    br;
    // double x = 0.5 * 1 + (1 - 0.5) * 0;
    // pr x;
    // sp;
}

int main(){
    // test_case
    solve();
    return 0;
}



Measured memory_bytes: 71168
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <stack> // s.top()
#include <bitset>
#include <queue> // s.front()
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define print(x) cout<<(x)<<endl
#define INF10 10000000000
#define INF5 100000
#define EPS 1e-10
#define MOD 1000000007

int table[2010][2010];
int H, W;


int maxim;


int main(){
	cin >> H >> W;
	for (int i = 0; i < H; i++) {
		string s; cin >> s;
		for (int j = 0; j < W; j++) {
			if (s[j] == '#')table[i][j] = -1;
		}
		//outofrange
		table[i][W] = -1;
	}
	//outofrange
	for (int j = 0; j < W; j++) {
		table[H][j] = -1;
	}

	// ->
	for (int i = 0; i < H; i++) {
		int sp = 0;
		int cnt = 0;

		for (int j = 0; j <= W; j++) {
			if (table[i][j] == -1) {
				for (int k = sp; k < j; k++)  {
					table[i][k] += cnt;
					maxim = max(maxim, table[i][k]);
				}
				cnt = 0;
				sp = j+1;
			}
			else {
				cnt++;
			}
		}
	}
	// sita
	for (int j = 0; j < W; j++) {
		int sp = 0;
		int cnt = 0;

		for (int i = 0; i <= H; i++) {
			if (table[i][j] == -1) {
				for (int k = sp; k < i; k++)  {
					table[k][j] += cnt;
					maxim = max(maxim, table[k][j]);
				}
				cnt = 0;
				sp = i+1;
			}
			else {
				cnt++;
			}
		}
	}


	print(maxim-1);




	return 0;
}

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

int main() {
  int n;
  cin >> n;
  
  double d = 0;
  for(int i=0; i<n; i++) {
    double a;
    cin >> a;
    d += 1 / a;
  }
  
  cout << 1 / d << endl;
}

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

#define int long long
#define ll long long
#define pb push_back

main(){
    int x;
    cin >> x;
    int ans = 100;
    int uy = 0;
    while (ans < x){
        uy++;
        ans += ans / 100;
    }
    cout << uy;
}


Measured memory_bytes: 3632
#include <stdio.h>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <iterator>
#include <assert.h>
#pragma warning(disable:4996) 
 
typedef long long ll;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF 9223300000000000000
#define INF 2140000000
const long long MOD = 1000000007;
//const long long MOD = 998244353;
using namespace std;


int main(int argc, char* argv[])
{
    int k,t;
    scanf("%d%d", &k, &t);

    int max=0;
    int i;
    for(i=0; i<t; i++) {
        int a;
        scanf("%d", &a);
        max=MAX(max,a);
    }
    if(max<=(k+1)/2) {
        printf("0\n");
    }
    else {
        int tmp=max-(k+1)/2;
        if(k%2==0) {
            printf("%d\n", tmp*2-1);
        }
        else {
            printf("%d\n", tmp*2);
        }
    }

    return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <iomanip>
#include <stdio.h>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <math.h>
#include <complex>
using namespace std;

int main() {
  int H, W; cin >> H >> W;
  vector<string> S(H);
  for (int i = 0; i < H; i++) cin >> S[i];
  // for (int i = 0; i < H; i++) cout << S[i] << endl;
  vector< vector<int> > line(H, vector<int>(W, 0)), column(H, vector<int>(W, 0));
  for (int i = 0; i < H; i++) {
    int s = 0, j = 0;
    while (j < W) {
      while (j < W) {
        if (S[i][j] == '#') break;
        j++;
      }
      int num = j - s;
      for (int k = s; k < j; k++) line[i][k] = num;
      j++;
      s = j;
    }
  }

  for (int j = 0; j < W; j++) {
    int s = 0, i = 0;
    while (i < H) {
      while (i < H) {
        if (S[i][j] == '#') break;
        i++;
      }
      int num = i - s;
      for (int k = s; k < i; k++) column[k][j] = num;
      i++;
      s = i;
    }
  }

  int ans = -1;
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      if (S[i][j] == '#') continue;
      ans = max(ans, line[i][j] + column[i][j]);
    }
  }
  cout << ans - 1 << endl;
}

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

using namespace std;

using i64 = int64_t;

const i64 MOD = 1e9+7;

const i64 INF = 1e18+7;


const i64 N = 1e3;

signed main(){

    vector<i64> aa;
    vector<i64> bb(N, -1);
    bb[0] = 0;
    bb[1] = 1;
    function<i64(int)> f = [&](int x){
        if(bb[x] != -1)
            return bb[x];
        if(x & 1)
            return bb[x] = (f(x / 2) + f(x / 2 + 1)) % MOD;
        else
            return bb[x] = f(x / 2);
    };

    for(int i = 0; i < N; ++i)
        f(i);
    vector<int> c(1, 0);
    for(auto& x : bb)
        c.emplace_back((c.back() + x) % MOD);

    i64 n;
    cin >> n;

    unordered_map<int,i64> m;

    m[0] = 0;
    m[1] = 1;

    function<i64(i64)> g = [&](i64 x){
        if(m.find(x) != m.end())
            return m[x];

        if(x & 1){
            return m[x] = (2 * g(x >> 1) + g((x >> 1) + 1)) % MOD;
        }else{
            return m[x] = (2 * g(x >> 1) + g((x >> 1) - 1)) % MOD;
        }
    };

    cout << g(n + 1) << endl;
    return 0;

}


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

int main()
{ 
  int n ;
  cin >> n ;
  vector<int> data(n) ;
  for(int i = 0 ; i < n ; i++)
  {
    cin >> data.at(i) ;
  }
  sort(data.begin(), data.end()) ;

  cout << data.at(n / 2) - data.at(n / 2 - 1) << endl ;
}


Measured memory_bytes: 640
fun main(args: Array<String>) {
    val s = readLine() ?: return
    val l = s.length
    val v = Array(l + 1) { 0L }

    var current = s[0]
    var count = 1
    1.until(l).forEach { i ->
        val c = s[i]
        when (current) {
            '<' -> {
                if (c == '>') {
                    (count).downTo(0).forEach {
                        v[i - it] = Math.max(v[i - it], (count - it).toLong())
                    }
                    current = c
                    count = 1
                } else {
                    count++
                }
            }
            '>' -> {
                if (c == '<') {
                    (count).downTo(0).forEach {
                        v[i - it] = Math.max(v[i - it], it.toLong())
                    }
                    current = c
                    count = 1
                } else {
                    count++
                }
            }
        }
    }
    if (s.last() == '>') {
        (count).downTo(0).forEach {
            v[l - it] = Math.max(v[l - it], it.toLong())
        }
    } else {
        (count).downTo(0).forEach {
            v[l - it] = Math.max(v[l - it], count - it.toLong())
        }
    }
    println(v.sum().toString())
}


Measured memory_bytes: 48728
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
#define endl "\n"
#define fi first
#define se second
#define For(i,a,b) for(ll i=a;i<b;i++)
#define sz size()
#define PQ priority_queue
#define len length()
#define mll map<ll,ll>
#define vll vector<ll>
#define vpll vector<pair<ll,ll> >
#define mp(x,y)  make_pair(x,y)
#define pb push_back
#define pf push_front
#define ALL(v) v.begin(),v.end()
#define LAPAK ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;

const ll MOD = 1000000007;

int main() {
	ll n;
	cin>>n;
	ll a[n];
	For(i,0,n)cin>>a[i];
	ll dp[n+2];
	dp[0]=0;
	dp[1]=abs(a[1]-a[0]);
	For(i,2,n){
	    dp[i]=min(abs(a[i]-a[i-1])+dp[i-1],abs(a[i]-a[i-2])+dp[i-2]);
	}
	cout<<dp[n-1];
	return 0;
}

/*            *          *******        *       *     *
             * *            *          * *       *   *
coded by    *****           *         *****       * *
           *     *      *   *        *     *       *
          *       *      * *        *       *      *
*/


Measured memory_bytes: 1792
#include<algorithm>     //sort,二分探索,など
#include<bitset>        //固定長bit集合
#include<cmath>         //pow,logなど
#include<complex>       //複素数
#include<deque>         //両端アクセスのキュー
#include<functional>    //sortのgreater
#include<iomanip>       //setprecision(浮動小数点の出力の誤差)
#include<iostream>      //入出力
#include<iterator>      //集合演算(積集合,和集合,差集合など)
#include<map>           //map(辞書)
#include<numeric>       //iota(整数列の生成),gcdとlcm(c++17)
#include<queue>         //キュー
#include<set>           //集合
#include<stack>         //スタック
#include<string>        //文字列
#include<unordered_map> //イテレータあるけど順序保持しないmap
#include<unordered_set> //イテレータあるけど順序保持しないset
#include<utility>       //pair
#include<vector>        //可変長配列

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvll;
typedef vector<vector<string>> vvs;
typedef vector<vector<bool>> vvb;
const ll MOD = 1000000007;
const ll INF = 1000000000000000000;
#define rep(i,n) for(int i=0;i<n;i++)
#define repl(i,s,e) for(int i=s;i<e;i++)
#define reple(i,s,e) for(int i=s;i<=e;i++)
#define revrep(i,n) for(int i=n-1;i>=0;i--)
#define all(x) (x).begin(),(x).end()

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()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int A, B, C, K;
    cin >> A >> B >> C >> K;

    int count = 0;
    while (A >= B)
    {
        B *= 2;
        count++;
    }

    while (B >= C)
    {
        C *= 2;
        count++;
    }

    if (count <= K)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 3648
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
const int dx[4] ={1,0,-1,0};
const int dy[4]={0,1,0,-1};
int main()
{
	ll h,w,cx,cy,dx,dy;
    cin>>h>>w>>cx>>cy>>dx>>dy;
    cx--;
    cy--;
    dx--;
    dy--;
    string s[h];
    for(ll i=0;i<h;i++)
		cin>>s[i];
    deque<P> que;
    que.push_back(P(cx,cy));
    bool visited[h][w];
    ll d[h][w];
    for (ll i=0;i<h;i++)
	{
        fill(visited[i],visited[i]+w,false);
        fill(d[i],d[i]+w,INT_MAX);
    }
    d[cx][cy]=0;
    visited[cx][cy]=true;
    while(!que.empty())
    {
    	P p=que.front();
    	ll X=p.first,Y=p.second;
    	if(X==dx&&Y==dy)
    	{
    		cout<<d[X][Y]<<endl;
    		return 0;
    	}
    	visited[X][Y]=1;
    	que.pop_front();
    	for(ll i=-2;i<3;i++)
    	{
    		for(ll j=-2;j<3;j++)
    		{
    			ll x=X+i,y=Y+j;
    			if(x<h&&x>=0&&y<w&&y>=0&&s[x][y]=='.')
    			{
    				if(visited[x][y])
    					continue;
    				if(abs(i)+abs(j)<2)
    				{
    					que.push_front(P(x,y));
    					d[x][y]=d[X][Y];
    					visited[i][j]=1;
    				}
    				else
    				{
    					if(d[X][Y]+1<d[x][y])
    					{
    						d[x][y]=d[X][Y]+1;
    						que.push_back(P(x,y));
    					}
    				}
    			}
    		}
    	}
    }
    cout<<-1<<endl;
    return 0;
}

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

using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
typedef vector<int> Vi;
//typedef tuple<int, int, int> T;
#define FOR(i,s,x) for(int i=s;i<(int)(x);i++)
#define REP(i,x) FOR(i,0,x)
#define ALL(c) c.begin(), c.end()
#define DUMP( x ) cerr << #x << " = " << ( x ) << endl
#define UNIQUE(c) sort(ALL(c)), c.erase(unique(ALL(c)), c.end())

const int dr[4] = {-1, 0, 1, 0};
const int dc[4] = {0, 1, 0, -1};

int main() {
  // use scanf in CodeForces!
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  int N; cin >> N;
  vector<set<int>> edges(N);
  REP(i, N-1) {
    int a, b; cin >> a >> b; a--, b--;
    edges[a].insert(b);
    edges[b].insert(a);
  }
  queue<int> degs;
  REP(i, N) {
    if (edges[i].size() == 1) degs.emplace(i);
  }

  vector<int> C(N); REP(i, N) cin >> C[i];
  sort(ALL(C));
  vector<int> ans(N, 0);

  int now = 0;

  while (degs.size() > 0) {
    int idx = degs.front(); degs.pop();
    //cout << idx << endl;
    ans[idx] = C[now++];
    if (edges[idx].size() > 0) {
      int nei = *edges[idx].begin();
      edges[nei].erase(idx);
      if (edges[nei].size() == 1) degs.emplace(nei);
    }
  }

  cout << accumulate(ALL(C), 0) - C.back() << endl;
  REP(i, N) cout << ans[i] << (i == N - 1 ? '\n' : ' ');
  return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
    ll n,i;
    cin>>n;
    ll x[n],y[n];
    for(i=0;i<n;i++)
    {
        cin>>x[i];
    }
    for(i=0;i<n;i++)
    {
        if(i==0)
        {
            y[i]=0;
            
        }
        else if(i==1)
        {
            y[i]=(abs(x[i]-x[i-1]));
        }
        else
        {
            y[i]=min(y[i-1]+abs(x[i]-x[i-1]),y[i-2]+abs(x[i]-x[i-2]));
        }

        
    }
    cout<<y[n-1]<<"\n";
}   

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

As = []
As.append([int(x) for x in input().split()])
As.append([int(x) for x in input().split()])

def dfs(row,column,sum):
    if row == 1:
        if column == N - 1:
            return sum + As[row][column]
        else:
            return dfs(row,column + 1,sum + As[row][column])
    else:
        if column == N - 1:
            return dfs(row + 1,column,sum + As[row][column])
        else:
            return max(dfs(row + 1,column, sum + As[row][column]),dfs(row,column + 1,sum + As[row][column]))

print(dfs(0,0,0))


Measured memory_bytes: 3064
#include <iostream>
using namespace std;
int main()
{
	int S,h,m,s;
	cin >> S;
	h = S / 3600;
	m = S / 60 % 60;
	s = S % 60;
	cout << h << ":" << m << ":" << s << endl;
	return 0;
} 


Measured memory_bytes: 3088
#include <bits/stdc++.h>
#define rep(k,n) for (int k = 0; k < (int)(n); k++)
#define REP(k,n) for (int k = 1; k < (int)(n); k++)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define vout(x) rep(k,x.size()) cout << x[k] << " "
template<class T> bool chmin(T &a, T b) {if(a>b) {a=b;return 1;}return 0;}
template<class T> bool chmax(T &a, T b) {if(a<b) {a=b;return 1;}return 0;}
using namespace std;
using vint = vector<int>;
using vvint = vector<vector<int>>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<int,int>;
const int inf = 1e9;
const ll inf_l = 1e18;
const int MAX = 1e5;

map<ll,ll> mp;
ll a, b, c, d;

ll dfs(ll n) {
    if (mp.find(n) != mp.end()) return mp[n];
    else {
        ll res;
        if (inf_l/n < d) res = inf_l;
        else res = d*n;
        chmin(res,dfs((n+1)/2)+a+d*(n%2));
        chmin(res,dfs(n/2)+a+d*(n%2));
        chmin(res,dfs((n+2)/3)+b+d*(3-n%3));
        chmin(res,dfs(n/3)+b+d*(n%3));
        chmin(res,dfs((n+4)/5)+c+d*(5-n%5));
        chmin(res,dfs(n/5)+c+d*(n%5));
        return mp[n] = res;
    }
}

int main() {
    int t; cin >> t;
    rep(i,t) {
        ll n; cin >> n;
        cin >> a >> b >> c >> d;
        mp.clear();
        mp[0] = 0; mp[1] = d;
        cout << dfs(n) << endl;
    }
}

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

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	int N;
	cin >> N;
	float result = (float)((1 + N) / 2.0) * N;
	cout << (int) result;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const long long INF = 9999999997;
int main() {
    long long N, K; cin >> N >> K;
    vector<long long>A(N);
    for (long long i = 0; i < N; i++) {
        cin >> A.at(i);
    }
    vector<long long>DP(110000, INF);
    DP.at(0) = 0;
    for (long long i = 1; i < N; i++) {
        long long num = INF;
        for (long long j = 1; j <= K; j++) {
            if (i - j < 0) continue;
            num = min(num, DP.at(i - j) + abs(A.at(i - j) - A.at(i)));
        }
        DP.at(i) = num;
    }
    cout << DP.at(N - 1) << endl;
}

Measured memory_bytes: 4816
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define inf LLONG_MAX
#define pll pair <ll,ll>
#define min_pq priority_queue <pll> ,vector <pll>, greater <pll> > > 
#define f first
#define s second

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

	ll n,m;
	cin>>n>>m;
	if(n<m)
	{
		for(ll i=0;i<m;i++)
			cout<<n;
		cout<<'\n';
	}
	else
	{
		for(ll i=0;i<n;i++)
			cout<<m;
		cout<<'\n';
	}
}


Measured memory_bytes: 256
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <functional>
#include <numeric>
#include <math.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main(void) {
	ll N;
	cin >> N;
	ll ans = 0;
	for (ll i = 1; i <= N; i++) {
		ll tmp = N / i;
		ans += i * (tmp*(tmp + 1) / 2);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3604
W,H,N = list(map(int,input().split()))

points = [list(map(int, input().split())) for _ in range(N)]
res = 0

x1,y1 = [0,0]
x2,y2 = [W,H]

for x,y,a in points:
    if a == 1:
        x1 = max(x1, x)
    if a == 2:
        x2 = min(x2, x)
    if a == 3:
        y1 = max(y1, y)
    if a == 4:
        y2 = min(y2, y)

if x2-x1 <= 0 or y2-y1 <=0:
    print("0")
else:
    print((x2-x1)*(y2-y1))

Measured memory_bytes: 3064
import fractions
from functools import reduce
from sys import stdin
N, X = [int(_) for _ in stdin.readline().rstrip().split()]
xs = [int(_) for _ in stdin.readline().rstrip().split()]
xs.sort()
diff = [xs[i] - xs[i-1] if i > 0 else abs(xs[i]-X) for i in range(N)]
gcd = reduce(fractions.gcd, diff)
print(gcd)

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

int main() {
	int n;
	cin >> n;
	vector<int> c(n + 1);
	int ans = 0;
	for (int i = 0, a; i < n; i++) {
		cin >> a;
		if (a > n)
			ans++;
		else
			c[a]++;
	}

	for (int i = 0; i < n + 1; i++) {
		if (c[i] < i)
			ans += c[i];
		if (c[i] > i)
			ans += c[i] - i;
	}

	cout << ans << endl;
}


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

long long k;

int main(void){
  cin >> k;
  if(k < 50){
    cout << 50 << endl;
    for(int i = 0; i < 49; i++){
      cout << 0 << " ";
    }
    cout << 50 * k << endl;
  }
  else{
    cout << 50 << endl;
    long long m = k / 50;
    long long p = k % 50;
    for(int i = 0; i < k - 50 * m; i++){
      cout << 100 + 51 * m - k << " ";
    }
    for(int i = 0; i < 50 * (m + 1) - k; i++){
      cout << 49 + m - p ;
      if(i != 50 * (m + 1) - k - 1){
	cout << " ";
      }
    }
    cout << endl;
  }
}


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

cake_price = 4
donut_price = 7

max_cake = N // cake_price
max_donut = N // donut_price

isJustN = False
if max_cake * cake_price == N or max_donut * donut_price == N:
    isJustN = True
else:
    for c in range(1, max_cake + 1):
        for d in range(1, max_donut + 1):
            total_price = cake_price * c + donut_price * d
            if total_price == N:
                isJustN = True
                break

Result = ''
if isJustN == True:
    Result = 'Yes'
else:
    Result = 'No'
print(Result)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
#include <iomanip>
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF=1001001001;

int main() {
  string s;
  cin>>s;
  map<int,int>k;
  for(int i=0;i<s.size();i++){
    k[s[i]]++;
  }
  if(k['N']>0&&k['S']==0){cout<<"No"<<endl;}
  else if(k['S']>0&&k['N']==0){cout<<"No"<<endl;}
  else if(k['W']>0&&k['E']==0){cout<<"No"<<endl;}
  else if(k['E']>0&&k['W']==0){cout<<"No"<<endl;}
  else{cout<<"Yes"<<endl;}
  return 0;  
}

Measured memory_bytes: 3628