akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

#define LL long long
#define LB long double
#define ull unsigned long long
#define x first
#define y second
#define pb push_back
#define pf push_front
#define mp make_pair
#define Pair pair<int,int>
#define pLL pair<LL,LL>
#define pii pair<double,double>

const int INF=2e9;
const LL LINF=2e16;
const int magic=348;
const int MOD=1e9+7;
const double eps=1e-10;
const double pi=acos(-1);

struct fastio
{
	static const int S=1e7;
	char rbuf[S+48],wbuf[S+48];int rpos,wpos,len;
	fastio() {rpos=len=wpos=0;}
	inline char Getchar()
	{
		if (rpos==len) rpos=0,len=fread(rbuf,1,S,stdin);
		if (!len) return EOF;
		return rbuf[rpos++];
	}
	template <class T> inline void Get(T &x)
	{
		char ch;bool f;T res;
		while (!isdigit(ch=Getchar()) && ch!='-') {}
		if (ch=='-') f=false,res=0; else f=true,res=ch-'0';
		while (isdigit(ch=Getchar())) res=res*10+ch-'0';
		x=(f?res:-res);
	}
	inline void getstring(char *s)
	{
		char ch;
		while ((ch=Getchar())<=32) {}
		for (;ch>32;ch=Getchar()) *s++=ch;
		*s='\0';
	}
	inline void flush() {fwrite(wbuf,1,wpos,stdout);fflush(stdout);wpos=0;}
	inline void Writechar(char ch)
	{
		if (wpos==S) flush();
		wbuf[wpos++]=ch;
	}
	template <class T> inline void Print(T x,char ch)
	{
		char s[20];int pt=0;
		if (x==0) s[++pt]='0';
		else
		{
			if (x<0) Writechar('-'),x=-x;
			while (x) s[++pt]='0'+x%10,x/=10;
		}
		while (pt) Writechar(s[pt--]);
		Writechar(ch);
	}
	inline void printstring(char *s)
	{
		int pt=1;
		while (s[pt]!='\0') Writechar(s[pt++]);
	}
}io;

const int MAXN=4000;

inline int add (int x) {if (x>=MOD) x-=MOD;return x;}
inline int sub (int x) {if (x<0) x+=MOD;return x;}

int n,m,k;
int dp[MAXN+48][MAXN+48],sum[MAXN+48][MAXN+48];

int main ()
{
	io.Get(n);io.Get(m);io.Get(k);
	dp[0][0]=1;int ans=0;
	for (register int i=0;i<=m;i++) sum[0][i]=1;
	for (register int i=1;i<=n+m;i++)
		for (register int j=0;j<=m;j++)
		{
			dp[i][j]=sub(sum[i-1][j]-((j-(k-1)>0)?sum[i-1][j-(k-1)-1]:0));
			sum[i][j]=(j==0?dp[i][j]:add(sum[i][j-1]+dp[i][j]));
			if (j && j%(k-1)==m%(k-1) && (k-1)*i-j>=0 && (k-1)*i-j<=n-1 && ((k-1)*i-j)%(k-1)==(n-1)%(k-1))
				ans=add(ans+sub(dp[i][j]-dp[i-1][j]));
		}
	io.Print(ans,'\n');
	io.flush();return 0;
}

Measured memory_bytes: 130816
#include <bits/stdc++.h>
#define R register
#define mp make_pair
#define ll long long
#define pii pair<int, int>
using namespace std;
const int N = 110;

int n, m, tab[N][N], f[N][N];
char s[N];

template <class T>
inline void read(T &x) {
	x = 0;
	char ch = getchar(), w = 0;
	while (!isdigit(ch)) w = (ch == '-'), ch = getchar();
	while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
	x = w ? -x : x;
	return;
}

int main() {
	read(n), read(m);
	for (R int i = 1; i <= n; ++i) {
		scanf("%s", s + 1);
		for (R int j = 1; j <= m; ++j)
			tab[i][j] = s[j] == '#';
	}
	memset(f, 0x3f, sizeof (f));
	f[1][1] = tab[1][1];
	for (R int i = 1; i <= n; ++i) {
		for (R int j = 1; j <= m; ++j) {
			if (i > 1)
				f[i][j] = min(f[i][j], f[i - 1][j] + (tab[i][j] != tab[i - 1][j]));
			if (j > 1)
				f[i][j] = min(f[i][j], f[i][j - 1] + (tab[i][j] != tab[i][j - 1]));
		}
	}
	cout << (f[n][m] + 1) / 2 << endl;
	return 0;
}

Measured memory_bytes: 384
import sys
input = sys.stdin.readline

Days = int(input())
C = list(map(int, input().split())) # 満足度低下
Ss = [list(map(int, input().split())) for _ in range(Days)]
# Ss[d][i]: d日目にiを開催したときの満足度
T = [int(input()) for _ in range(Days)] # 開催するコンテスト
Q = int(input())
Query = [list(map(int, input().split())) for _ in range(Q)]

INF = 10**18

def outputToScore(T):
    last = [0]*26
    used = [[] for _ in range(26)]
    satisfied = 0
    for d, t in enumerate(T):
        t -= 1; d += 1
        satisfied += Ss[d-1][t]
        used[t].append(d)
        last[t] = d
        for i, c in enumerate(C):
            satisfied -= c*(d-last[i])
        # print(satisfied)
    return satisfied, used

Satisfied, Used = outputToScore(T)
for d, aft in Query:
    aft -= 1
    bef = T[d-1]-1
    deltaSatis = Ss[d-1][aft] - Ss[d-1][bef]
    # d日目のコンテストをbefからaftに変える

    # bi-1 -> bi -> bi+1 を bi-1 -> bi+1
    befind = Used[bef].index(d)
    befday0 = 0 if befind == 0 else Used[bef][befind-1]
    befday2 = Days+1 if befind == len(Used[bef])-1 else Used[bef][befind+1]
    
    befd01 = d - befday0
    befd12 = befday2 - d
    befd02 = befday2-befday0
    deltaSatis -= C[bef]*(befd02*(befd02-1)//2) - C[bef]*(befd01*(befd01-1)//2 + befd12*(befd12-1)//2)

    # ai -> ai+1 を ai -> (insert) -> ai+1
    if len(Used[aft]) > 0:
        aftday0 = 0
        aftday2 = Days+1
        newaft = []
        for i,a in enumerate(Used[aft]):
            if a < d:
                aftday0 = a
            elif aftday2 == Days+1:
                newaft.append(d)
                aftday2 = a
            newaft.append(a)
        if aftday2 == Days+1:
            newaft.append(d)
        aftd01 = d - aftday0
        aftd12 = aftday2 - d
        aftd02 = aftd01 + aftd12
        deltaSatis += C[aft]*(aftd02*(aftd02-1)//2) - C[aft]*(aftd01*(aftd01-1)//2 + aftd12*(aftd12-1)//2)
    else:
        newaft = [d]
        d01 = d
        d12 = Days+1 - d
        deltaSatis += C[aft] * Days*(Days+1)//2 - C[aft]*(d01*(d01-1)//2 + d12*(d12-1)//2)

    Used[bef].remove(d)
    Used[aft] = newaft
    T[d-1] = aft+1
    Satisfied += deltaSatis
    print(Satisfied)



Measured memory_bytes: 88780
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<n;i++)
#include <bits/stdc++.h>
#include <numeric>
using namespace std;
typedef long long ll;
const int mod= 1e+9+7;

int main() {
    ll S,C; cin>>S>>C;
    ll ans =0;
    if(S>=C/2)cout<<C/2<<endl;
    else {
        ans +=S;
        ans +=(C/2-S)*2/4;
        cout<<ans<<endl;
    }

}

 



Measured memory_bytes: 256
// BEGINNING WITH THE NAME OF ALMIGHTY GOD ALLAH
// AUTHOR:: MOHAMMAD FAISAL
#include<bits/stdc++.h>
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.flush();
	map<char,int> mp;
  	mp['A'] = 10;mp['B'] = 11;mp['C'] = 12;mp['D'] = 13;mp['E'] = 14;mp['F'] = 15;
  	char a,b;
    cin >> a >> b;
    if(mp[a] > mp[b])
      cout<<">";
    if(mp[a]==mp[b])
      cout<<"=";
  	if(mp[a] < mp[b])
      cout<<"<";
	return 0;
	// BYE BYE 
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#define DEBUG(x) std::cout << '>' << #x << ':' << x << '\n';
#define PRINTVEC(x) for (int i = 0; i < (int)x.size(); i++) std::cout << x[i] << ' '; std::cout << '\n';
#define PRINTPAIR(x) for (int i = 0; i < (int)x.size(); i++) std::cout << x[i].first << ' ' << x[i].second << '\n'; std::cout << '\n';
#define PRINTSET(x) for (auto it = x.begin(); it != x.end(); it++) { std::cout << *it << ' '; } std::cout << '\n';
#define io std::ios_base::sync_with_stdio(false);std::cin.tie(NULL);   
const int INF = 1<<29;
typedef long long ll;
using namespace std;


int main()
{
	io;
    #ifndef ONLINE_JUDGE
    //freopen("input.txt", "r", stdin); 
    //freopen("output.txt", "w", stdout);  
    #endif

    int n;
    cin >> n;
    bool ok = false;
    while (n > 0) {
        if (n % 10 == 7)
            ok = true;
        n /= 10;
    }
    cout << (ok ? "Yes" : "No");

    #ifndef ONLINE_JUDGE   
    //std::cout << '\n' << "Time elapsed : " << 1.0 * clock() / CLOCKS_PER_SEC << " sec \n";
    #endif
    return 0;
}


Measured memory_bytes: 3664
#include <iostream>
#include <cstdio>
#include <string.h>
#include <vector>
#include <limits>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
#include <deque>
#include <set>
#include <map>
#include <queue>
#include <assert.h>
#include <sstream>
#include <type_traits>
#define SET(x,y) x |= (1 << y)
#define CLEAR(x,y) x &= ~(1<< y)
#define READ(x,y) ((0u == (x & (1<<y)))?0u:1u)
#define TOGGLE(x,y) (x ^= (1<<y))
#define watch(x) cout << (#x) << " is " << (x) << endl
#define pb push_back
#define mp make_pair
#define si(n) scanf("%d",&n)
#define sf(n) scanf("%f",&n)
#define sl(n) scanf("%lld",&n)
#define slu(n) scanf("%llu",&n)
#define sd(n) scanf("%lf",&n)
#define ss(n) scanf("%s",n)
#define pnl printf("\n")
#define ll long long
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pF first
#define pS second
#define CL(a,b) memset(a,b,sizeof(a))
#define sqr(x) ((x)*(x))
#define intLIMIT numeric_limits<int>
#define longLIMIT numeric_limits<long long>
#define GCD(a,b) __gcd((a),(b))
#define dbl(x) (double)(x)
#define vi vector <int>
#define vii vector < pair <int, int> >
#define vll vector <long long>
#define allof(x) (x).begin(), (x).end()
#define fastCin cin.sync_with_stdio(0);cin.tie(0)
#define scanUnsigned(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
#define printArr(a,l) cout<<#a<<": ";for(int i=0;i<(l);i++){cout<<a[i]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(int i=0;i<(r);i++){for(int j=0;j<(c);j++){cout<<a[i][j]<<" ";}cout<<endl;}
char _;
using namespace std;
void PRINT (int x, int y) { for (int i = y-1; i >= 0; i--) { cout << READ(x,i); } cout << endl; }

vector<string>vec_splitter(string s){s+=',';vector<string>res;while(!s.empty()){res.push_back(s.substr(0,s.find(',')));s=s.substr(s.find(',')+1);}
return res;}
void debug_out(vector<string>__attribute__((unused))args,__attribute__((unused))int idx,__attribute__((unused))int LINE_NUM){cerr<<endl;}
template<typename Head,typename...Tail>void debug_out(vector<string>args,int idx,int LINE_NUM,Head H,Tail...T){if(idx>0)cerr<<", ";else cerr<<"Line("<<LINE_NUM<<") ";stringstream ss;ss<<H;cerr<<args[idx]<<" = "<<ss.str();debug_out(args,idx+1,LINE_NUM,T...);}
#ifdef LOCAL_DBG
#define dbg(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define dbg(...) 42
#endif

int main () {
	fastCin;
	string s, t;
	cin >> s >> t;
	int cnt = 0;
	for (int x = 0; x < s.length(); x++) {
		if (s[x] != t[x]) {
			cnt++;
		}
	}
	cout << cnt << "\n";
	return 0;
}

Measured memory_bytes: 3464
import java.lang.Math
fun main(args: Array<String>) {
    val (N, K) = readLine()!!.split(" ").map(String::toInt)
    val S = readLine()!!.toMutableList()
    for (i in 0 until S.size) {
        if (S[i] == '0') break
        S[i] = '0'
    }
    for (i in S.size-1 downTo 0) {
        if (S[i] == '0') break
        S[i] = '0'
    }
    val cnt = mutableListOf<Int>()
    cnt.add(1)
    for (i in 1 until S.size) {
        if (S[i] != S[i - 1]) {
            cnt.add(cnt[cnt.size-1])
        }
        cnt[cnt.size-1] += 1
    }
    var ans = cnt[Math.min(cnt.size-1, 2 * K - 1)]
    for (i in 1 until cnt.size step 2) {
        val ri = Math.min(cnt.size - 1, i + 2 * K)
        ans = Math.max(ans, cnt[ri] - cnt[i - 1])
    }
    println(ans)
}

Measured memory_bytes: 41660
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;

public class Main {
    private static Scanner sc;

    public Main() {
    }

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

    }

    List ex;

    private void solve() {
        int N = sc.nextInt();
        ex = new ArrayList<>();
        int base = 0;
        int exNum = 0;
        Set used = new HashSet();
        for (int i = 0; i < N; i++) {
            String s = getRate(sc.nextInt());
            if ("EX".equals(s)) {
                exNum++;
                continue;
            }
            used.add(s);
        }

        base = used.size();
        if (0 < base) {
            System.out.println(base + " " + (base + exNum));
        } else {
            System.out.println(1 + " " + exNum);
        }
    }

    private String getRate(int r) {
        String ret = "";

        if (1 <= r && r <= 399) {

        } else if (400 <= r && r <= 799) {
            ret = "A";
        } else if (800 <= r && r <= 1199) {
            ret = "B";
        } else if (1200 <= r && r <= 1599) {
            ret = "C";
        } else if (1600 <= r && r <= 1999) {
            ret = "D";
        } else if (2000 <= r && r <= 2399) {
            ret = "E";
        } else if (2400 <= r && r <= 2799) {
            ret = "F";
        } else if (2800 <= r && r <= 3199) {
            ret = "G";
        } else {
            ret = "EX";
        }
        return ret;
    }
}


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

int main() {
  int N, M;
  cin >> N >> M;
  int a[M], b[M], c[M], dist[N][N];
  for (int i=0; i<M; i++) {
    cin >> a[i] >> b[i] >> c[i];
    a[i]--;
    b[i]--;
  }
  const int inf=1e9;
  for (int i=0; i<N; i++) {
    for (int j=0; j<N; j++) {
      dist[i][j]=inf;
    }
    dist[i][i]=0;
  }
  for (int i=0; i<M; i++) {
    dist[a[i]][b[i]]=min(dist[a[i]][b[i]],c[i]);
    dist[b[i]][a[i]]=min(dist[b[i]][a[i]],c[i]);
  }
  for (int k=0; k<N; k++) {
    for (int i=0; i<N; i++) {
      for (int j=0; j<N; j++) {
        dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
      }
    }
  }
  int ans=M;
  for (int i=0; i<M; i++) {
    bool shortest=false;
    for (int j=0; j<N; j++) {
      if (dist[j][a[i]]+c[i]==dist[j][b[i]]) {
        shortest=true;
      }
    }
    if (shortest) {
      ans--;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
s = input()
k = int(input())
subs = []
for i in range(len(s)):
    for j in range(5):
        if s[i:i+j+1] not in subs:
            subs.append(s[i:i+j+1])
subs = sorted(subs)
# print(subs)
print(subs[k-1])

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

int main(void){
	ll n,m;
	cin>>n>>m;
	ll l[m],r[m];
	//vector<pair<ll,ll>> a(m+1);
	for(ll i=0;i<m;i++){
		cin>>l[i]>>r[i];
		//a.push_back(make_pair(l[i],r[i]));
	}
	sort(l,l+m);
	sort(r,r+m);
	ll ans = r[0] - l[m-1] + 1;
	if(ans<0)ans=0;
	cout<<ans<<endl;
}


Measured memory_bytes: 1792
module Main where

import Data.Functor
import Data.List

main :: IO ()
main = do
  { [ss] <- getInts
  ; let (mm,s) = ss `divMod` 60
  ; let (h,m)  = mm `divMod` 60
  ; putStrLn (intercalate ":" (map show [h,m,s]))
  }

getInts :: IO [Int]
getInts = do
  { line <- getLine
  ; let ints = map readInt (words line)
  ; return ints
  }

getInts' :: IO [Int]
getInts' = do
  { line <- getLine
  ; return (map readInt (words line))
  }

getInts'' :: IO [Int]
getInts'' = map readInt . words <$> getLine

readInt :: String -> Int
readInt = read

Measured memory_bytes: 3524
a,b,c = map(int,input().split())

if any((a%2==1,b%2==1,c%2==1)):
    print(0)
    exit()
    
cnt = 0
while cnt <= 100:
    a,b,c = (b+c)/2, (a+c)/2,(a+b)/2
    cnt += 1
    if any((a%1!=0,b%1!=0,c%1!=0)):
        print(cnt-1)
        exit()
print(-1)

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

int main(){
  int N;
  string s;
  cin>>N>>s;
  int r=0;
  for(char &c:s)
    if(c=='R')
      r++;
  if(r>N-r)
    cout<<"Yes"<<endl;
  else
    cout<<"No"<<endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
const ld eps = 1e-9;


int solve(int l, int r, const string& st,vector<vector<int>>&memo,vector<vector<int>>&flags) {
	if (memo[l][r] == -1) {
		if(l==r)memo[l][r]=0;
		else if(l+1==r)memo[l][r]=1;
		else {

			if (st[l] == st[r - 1]) {
				memo[l][r]=2+solve(l+1,r-1,st,memo,flags);
				flags[l][r]=3;
			}
			else {
				int lk=solve(l+1,r,st,memo,flags);
				int rk=solve(l,r-1,st,memo,flags);

				if (lk > rk) {
					flags[l][r]=2;
				}
				else {
					flags[l][r]=1;
				}
				memo[l][r]=max(lk,rk);
			}
		}
	}
	return memo[l][r];
}

int main() {
	string st;
	while (cin>>st) {
		vector<vector<int>>memo(st.size()+1,vector<int>(st.size()+1,-1)),flags(st.size()+1,vector<int>(st.size()+1));
		int ans=solve(0,st.size(),st,memo,flags);
		string ans_st1,ans_st2;

		int al=0;
		int ar=st.size();
		while (true) {
			int num=flags[al][ar];
			if (num == 3) {
				ans_st1.push_back(st[al]);
				ans_st2.push_back(st[ar-1]);
				al++;
				ar--;
			}
			else if (num == 2) {
				al++;
			}
			else if (num == 1) {
				ar--;
			}
			else {
				if (al + 1 == ar) {
					ans_st1.push_back(st[al]);

				}
				break;
			}
		}
		reverse(ans_st2.begin(),ans_st2.end());
		cout<<ans_st1<<ans_st2<<endl;
	}
	return 0;
}


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

int main() {
  int x;
  cin >> x;
  
  int q=2000-x;
  
  
  int num=0;
  while(q>0){
    q=q-200;
    num++;
  }
    
    cout << num << endl;
    
}


Measured memory_bytes: 3632
#define rep(i, a, b) for(int i = a; i < b; i++)
#define rrep(i, a, b) for(int i = a; i <= b; i++)

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>

using namespace std;

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

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

int main(){
	char s[205];
	scanf("%s",s);
	int len=strlen(s);
	for(int j=len-2;j>=0;j-=2){
		bool f=1;
		for(int i=0;i<j/2;i++){
			//printf("s[%d]=%c s[%d]=%c\n",i,s[i],i+j/2,s[i+j/2]);
			if(s[i]!=s[i+j/2]){
				f=0;
				break;	
			}
		}
		if(f){
			printf("%d",j);
			return 0;
		}
	}
	
	return 0;
}

Measured memory_bytes: 128
#include <stdio.h>

int main()
{
	int N;
	scanf("%d", &N);
	int l[N], r[N];
	int i, j, k;
	for (i = 0; i < N; i++) {
		scanf("%d%d", &l[i], &r[i]);
	}
	int sum=0;
	for (i = 0; i < N; i++) {
		sum += r[i] - l[i] + 1;
	}
	printf("%d\n", sum);
	return 0;
}


Measured memory_bytes: 128
#include<iostream>
#include<stdio.h>
#include<math.h>
#define EPS (1e-10)
using namespace std;
int main(){
  double r,n;
  cin >> r >> n;
  while(r!=0||n!=0){
    int i,j,k;
    double xr,xl,h;
    double hs[41]={};
    for(i=0;i<n;i++){
      cin >> xr >> xl >> h;
      for(j=xr;j<xl;j++){
	hs[j+20]=max(hs[j+20],h);
      }
    }
    /*
    for(i=0;i<=40;i++) cout << hs[i] ;
    cout << endl;
    */
    double o=0;
    int f=0;
    while(f==0){
      o+=0.0001;
      int w;
      if(o<r){
	w = (int) sqrt((r*r)-(r-o)*(r-o));
	if(sqrt((r*r)-(r-o)*(r-o))-w>=EPS) w+=1;
      }
      else{
	w=r;
      }
      //cout << w << endl;
      for(j=-w;j<0;j++){
	if(hs[j+20]<o-r+sqrt((r*r)-((j+1)*(j+1)))){
	  //cout << w << ":" << o << ":" << hs[j+20]  << ":" <<  j << endl;
	  f=1;
	}
      }
      if(o-hs[20-1]>EPS){
	//cout << w << ":" << o << ":" << hs[20-1]  << endl;
	f=1;
      }
      if(o-hs[20]>EPS){
	//cout << w << ":" << o << ":" << hs[20] << endl;
	f=1;
      }
      for(j=1;j<w;j++){
	if(hs[j+20]<o-r+sqrt((r*r)-(j*j))){
	  //cout << w << ":" << o << ":" << hs[j+20]  << ":" <<  j << endl;
	  f=1;
	}
      }
    }
    
    printf("%.4f\n",o-0.0001);
    cin >> r >> n;
  }

}

Measured memory_bytes: 1240
#include "bits/stdc++.h"
#define REP(i, n) for(int i = 0; i < int(n); i++)
#define FOR(i,n,m) for(int i = int(n); i < int(m); i++)
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 6;
const ll LLINF = 1e18 + 1;

template<int mod>
struct mint {
private:
    long long x;
public:
    mint(long long x = 0) :x(x%mod) {}
    mint(std::string s) {
        long long z = 0;
        REP(i, s.size()) {
            z *= 10;
            z += s[i] - '0';
            z %= mod;
        }
        this->x = z;
    }
    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;
    }
    friend std::ostream& operator<<(std::ostream& os, const mint& n) {
        return os << n.x;
    }
    bool operator==(const mint a) const {
        return this->x == a.x;
    }
};

int main() {
    int n;
    ll k; cin >> n >> k;
    vector<int> a(n);
    REP(i, n) cin >> a[i];
    mint<MOD> b = 0, c = 0;
    REP(i, n) {
        REP(j, n) {
            if (i < j) {
                if (a[i] > a[j]) b += 1;
            }
            if (i != j) {
                if (a[i] > a[j]) c += 1;
            }
        }
    }
    cout << mint<MOD>(k*(k - 1) / 2)*c + b * k << endl;
    return 0;
}

Measured memory_bytes: 256
#!python3.4.3

N, M = map(int, input().split(' '))
A = list(map(int, input().split(' ')))

total = sum(A)

count = 0

for a in A:
  if not a < total/(4*M):
    count+=1

if count >= M:
  print("Yes")
else:
  print("No")    

Measured memory_bytes: 3060
#include <iostream>
#include <iomanip>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;

int main() {
    int a[3];
    int b[3];
    int y[3];
    int x[3];
    while(true) {
    REP(i,3)
        cin >> a[i];
    REP(i,3)
        cin >> b[i];
    if(!cin)
        return 0;
    double o[2];
        o[0] = b[1]*a[2] - a[1]*b[2];
        o[1] = -b[0]*a[2] + a[0]*b[2];
    REP(i,2)
        o[i] = (o[i]==0)?0:o[i]/(a[0]*b[1]-b[0]*a[1]);
    cout << fixed << setprecision(3) << o[0] << ' ';
    cout << fixed << setprecision(3) << o[1] << '\n';
    }
}

Measured memory_bytes: 1236
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(b) - 1;i>=(a);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)

#define PB push_back
#define INF (1<<29)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define CLR(a) memset(a,0,sizeof(a))
const int dx[] = {-1,0,0,1},dy[] = {0,1,-1,0};

typedef long long int ll;

using namespace std;

int main(){
    string s;
    cin >> s;
    int count[] = {0,0,0};
    char joi[] = { 'J' ,'O' ,'I'};
    int index = 0;
    int ans = 0;
    REP(i,s.size()){

	if(index == 2 && s[i] != 'I'){
	    if(count[0] >= count[1] && count[2] >= count[1] ){
		ans = max(ans,count[1]);
	    }
	}

	if(s[i] == joi[index]){
	    count[index]++;
	}else if(index <= 1 && s[i] == joi[index+1]){
	    index++;
	    count[index]++;
	}else if(s[i] == 'J'){
	    index = 0;
	    REP(i,3) count[i] = 0;
	    count[index]++;
	}else{
	    index = 0;
	    REP(i,3) count[i] = 0;
	}
    }
    if(count[0] >= count[1] && count[2] >= count[1] ){
	ans = max(ans,count[1]);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 2052
#include <algorithm>
#include <iterator>
#include <iostream>
#include <utility>
#include <string>
#include <vector>

using namespace std;

int main()
{
    int n;

    cin >> n;

    int out = 1;

    while(out <= n) {
        out *= 2;
    }

    cout << out / 2 << endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX=1e5+10;
ll l[200];
int solve(){
    int n=0,m=0;
    cin>>n;
    for (int i = 0; i < n; ++i) {
        cin>>l[i];
    }
    for(int i=0;i<n;i++){
        for (int j = i+1; j < n; ++j) {
            for (int k = j+1; k < n; ++k) {
                if (l[i]!=l[j]&&l[j]!=l[k]&&l[i]!=l[k]){
                  if ((l[i]+l[j]>l[k])&&(l[i]+l[k]>l[j])&&(l[k]+l[j]>l[i]))
                     m++;
                }
            }
        }
    }
    cout<<m<<endl;
    return 0;
}
int main(){
    int _=1;
    while(_--){
        solve();
    }
}

Measured memory_bytes: 3648
N, Y = map(int, input().split())
m = 10000,5000,1000
ans = -1,-1,-1
for i in range(N+1):
  for j in range(N-i+1):
    k = N-i-j
    if Y==m[0]*i+m[1]*j+m[2]*k:
      ans = i,j,k
      break
      
print(*ans)

Measured memory_bytes: 9188
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <vector>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)


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

	int n;
	n = s.size();
	
	vector<int> cnt(2019,0);

	int count = 0;
	int temp;
	int r = 0; //(i-1)桁目までの数 mod2019

	int r10 = 1; // 10^i mod2019

	//配列を逆順に
	reverse(s.begin(), s.end());
	//「0桁まで」の余りが0なので1にしておく
	cnt[0] = 1;

	rep(i,n){
		temp = s[i] - '0';
		r = (r + (temp * r10)) % 2019; //((i-1)桁目までの数) + i桁目 * 10^i mod2019
		count += cnt[r];               //同じ余りの桁の分だけ2019の倍数が取り出せる
		cnt[r]++;
		r10 = (r10 * 10) % 2019;

		//printf("%d桁目:%dまでの余り:%d, 同じ余りの桁:%d\n", i, temp, r, cnt[r]);
	}

	cout << count;

}


Measured memory_bytes: 3736
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize "03"
#pragma GCC target("sse4")

#define ll long long int
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define FRE freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
#define f(i,n) for(ll i=0;i<n;i++)
#define fa(i,a,n) for(ll i=a;a<n?i<n:i>=n;a<n?i+=1:i-=1)
#define loop(i,a, n) for(ll i = a; i <= n; i++)
#define loopb(i,a, n) for(ll i = a; i >= n; i--)
#define pb push_back
#define pf push_front
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define setmem(x, k) memset(x, k, sizeof(x))
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define PI 3.1415926535897932384626
#define MOD 1000000007
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int>	vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef long double ld;
// const ll N = 1e6+5;	
// ll a[N], b[N], dp[N], in[N], out[N], level[N], vis[N];
// vl g[N];
ll n, m, k;

ll dp[100005][3];

ll fun(vector<vector<ll>>& a, ll pos, ll idx){
	if(pos == n){
		return 0;
	}
	if (dp[pos][idx] != -1) return dp[pos][idx];
	ll mx;
	if(idx == 0)
		mx = a[pos][idx] + max(fun(a, pos + 1, 1), fun(a, pos + 1, 2));
	if(idx == 1)
		mx = a[pos][idx] + max(fun(a, pos + 1, 0), fun(a, pos + 1, 2));
	if(idx == 2)
		mx = a[pos][idx] + max(fun(a, pos + 1, 0), fun(a, pos + 1, 1));
	return dp[pos][idx] = mx;
}

void solve() {
	ll x, y, z, p, q, r;
	cin >> n;
	vector<vector<ll>> a(n, vector<ll> (3));
	f(i,n){
		cin >> a[i][0] >> a[i][1] >> a[i][2];
	}
	setmem(dp, -1);
	x = fun(a, 0, 0);
	y = fun(a, 0, 1);
	z = fun(a, 0, 2);
	cout << max(x, max(y, z));
}

int32_t main() {
	IOS
	ll T;
	// cin >> T;
	// while(T--)
		solve();
	cerr<<"Time elapsed : "<<clock()*1000.0/CLOCKS_PER_SEC<<"ms"<<'\n'; 
	return 0;
}

Measured memory_bytes: 14336
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
#include <limits.h>
#include <cmath>
#include <queue>
#include <map>
#include <iomanip>
#include <random>
#include <fstream>
#define rep(i, n) for (int i = 0; i < n; i++)
#define PI 3.14159265358979323846
#define MOD 1000000007
using namespace std;
using ll = long long;

const int MAX = 1000000;

ll 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;
}

ll gcd(ll a, ll b)
{
  ll r;
  while ((r = a % b))
  {
    a = b;
    b = r;
  }
  return b;
}

template <class T> struct cord{
  T x,y;
};

template <class T> double dist(cord<T> a, cord<T> b){
  T dx=a.x-b.x;
  T dy=a.y-b.y;
  return sqrt(dx*dx+dy*dy);
}

int main()
{

  //cout << fixed << setprecision(10);

  string c1,c2; cin >> c1 >> c2;
  if (c1[0]==c2[2]&&c1[1]==c2[1]&&c1[2]==c2[0]){
    cout << "YES";
  } else {
    cout << "NO";
  }

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define getMat(x, n, m, val) vector<vector<ll>> x(n, vector<ll> (m, val))
#define setp fixed<<setprecision // use it as cout<<setp(number of fractional digits in x)<<x;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
ll M=1000000000+7;
 
ll power(ll x,ll n)
{
    ll result=1;
    while(n>0)
    {
        if(n % 2 ==1)
            result=(result * x)%M;
        x=(x*x)%M;
        n=n/2;
    }
    return result;
}

ll dp[1005][1005];
ll n;

string fun(string s,ll sub=0){
    if(s.length()==0)return "";
    // if(s.length()==1){
    //     for(ll i=0;i<s[0]-'0'-sub;i++)s="("+s;
    //     for(ll i=0;i<s[0]-'0'-sub;i++)s=s+")";
    //     return s;
    // }
    ll mn=INT_MAX,mnind=-1;
    vector<ll>indv;
    for(ll i=0;i<s.length();i++){
        if(s[i]<mn){
            mn=s[i];
            mnind=i;
        }
    }
    for(ll i=0;i<s.length();i++){
        if(s[i]==mn){
            indv.pb(i);
        }
    }
    string ts="";
    if(indv[0]>0)ts+=fun(s.substr(0,indv[0]),mn-'0');
    for(ll i=0;i<indv.size()-1;i++){
        ts+=(mn);
        ts+=fun(s.substr(indv[i]+1,indv[i+1]-1-indv[i]),mn-'0');
    }
    ts+=(mn);
    if(indv[indv.size()-1]<s.length()-1)ts+=fun(s.substr(indv[indv.size()-1]+1,s.length()-indv[indv.size()-1]-1),mn-'0');
    for(ll i=0;i<mn-'0'-sub;i++)ts="("+ts;
    for(ll i=0;i<mn-'0'-sub;i++)ts=ts+")";
    return ts;
}


int main(){
    fastio;
    ll t=1,cno=0;
    // ll mod=998244353 ;
    // cin>>t;
    while(t--){
        ll n,m;
        cin>>n>>m;
        if(m>n)cout<<min(m-n,n);
        else cout<<min(n%m,m-n%m);
    }
}

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

const int NMAX = 510;

int n, m, q, x, y;
long a[NMAX][NMAX];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m >> q;
	for (int i = 1; i <= m; ++i){
		cin >> x >> y;
		a[x][y]++;
	}
	for(int i=1; i<n; ++i)
		for(int j=i+1; j<=n; ++j)
			a[i][j] += a[i][j-1];
	for (int i=1; i<=q; ++i){
		cin >> x >> y;
		long res = 0;
		for (int j=x; j<=y; ++j)
			res += a[j][y];
		cout << res << "\n";
	}
	return 0;
}

Measured memory_bytes: 2944
#!/usr/bin/env python3
import sys


def solve(A: int, B: int, C: int, K: int):
    print(max([A, B, C]) * (2 ** K) + sum([A, B, C]) - max([A, B, C]))


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    C = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    solve(A, B, C, K)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii =  pair<int, int>;
using pll =  pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
constexpr long long INF = 1000000009LL;
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define fo(i,j,n) for (int i=(j); i < (n); i++)
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; }


int main() {
    int n, k, s; cin >> n >> k;
    vector<int> A(n);
    rep(i, n){
        cin >> A[i];
        if(A[i] == 1) s = i;
    }

    int cnt = 0, pos = 0;
    while(pos < n-1){
        pos += k-1;
        cnt++;
    }
    cout << cnt << ln;
}

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


int main(){
    long long n,m,k;
    cin >> n >> m >> k;
    vector<long long> A(n+1,0);
    vector<long long> B(m+1,0);

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

    for(int i=1;i<m+1;i++){
        cin >> B[i];
        B[i]+=B[i-1];
    }

    int ans=0,j=m;

    for(int i=0;i<n+1;i++){
        if(A[i]>k){
            break;
        }
        while(B[j]>k-A[i]){
            j--;
        }
        ans = max(ans,i+j);
    }

    cout << ans << endl;
}

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

using namespace std;
int a[55];
int n;
bool check(){
	for(int i=1;i<n;i++){
		if(a[i]<a[i-1])return 0;
	}
	return 1;
}
int main(){
	cin>>n;
	for(int i=0;i<n;i++)cin>>a[i];
	for(int i=0;i<n;i++){
		for(int j=i;j<n;j++){
			swap(a[i],a[j]);
			if(check()){
				cout<<"YES";
				return 0;
			}
			swap(a[i],a[j]);
		}
	}
	cout<<"NO";
	return 0;
} 

Measured memory_bytes: 256
N=int(input())
array=list(map(int,input().split()))

X=[0]
for i in array:
    X.append(i)

INF=10000000

dp=[[INF for j in range(100+1)] for j in range(N+1)]

for i in range(100+1):
    dp[0][i]=0

for i in range(1,N+1):
    for j in range(1,100+1):
        dp[i][j]=min(dp[i][j],dp[i-1][j]+(X[i]-j)**2)
        
ans=INF
for i in range(1,100+1):
    ans=min(ans,dp[N][i])

print(ans)

Measured memory_bytes: 9336
#include<map>
#include<iostream>
#include<deque>
#include<algorithm>
#include<string>
#include<cctype>
#include<iomanip>
#include<vector>
#include<queue>
#include<tuple>
#include<stdio.h>
 
using namespace std;
#define REP(i,b,e) for(ll i=(ll)b;i<(ll)e;i++)
#define rep0(i,n) REP(i,0ll,n)
#define rep1(i,n) REP(i,1ll,n+1)
 
#define shosu setprecision(10)
 
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P,ll> Q;
typedef pair<Q,ll> R;
ll longinf=1ll<<60;
int inf=1<<29;
//mleしなければぜんぶllでかく。

int main(){
	char b;
	cin>>b;
	string s="ATACGC";
	for(int i=0;i<5;i++){
		if(s[i]==b){
			cout<<s[i+1]<<endl;
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
int main() {
 long long int a,b,c;
      
  cin >> a>>b>>c;
  
  long long int d =(a%2)*(b%2)*(c%2)*min({a*b,c*b,a*c});

  
  cout << d << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    long long int n,k,i;
    string s;
    cin>>n;
    cin>>s;
    if(s.length()<=n)cout<<s;
    else{
   for(i=0;i<n;i++)cout<<s[i];
   cout<<"...";
    }
    
}

Measured memory_bytes: 3596
#include <cstdio>
#include <cmath>
#include <iostream>
#include <set>
#include <algorithm>
#include <vector>
#include <map>
#include <cassert>
#include <string>
#include <cstring>
#include <queue>

using namespace std;

#define rep(i,a,b) for(int i = a; i < b; i++)
#define S(x) scanf("%d",&x)
#define S2(x,y) scanf("%d%d",&x,&y)
#define P(x) printf("%d\n",x)
#define all(v) v.begin(),v.end()
#define FF first
#define SS second

typedef long long int LL;
typedef pair<int, int > pii;
typedef vector<int > vi;

int X[11];

bool isGood(int x) {
  while(x) {
    int r = x % 10;
    if(X[r]) return false;
    x /= 10;
  }
  return true;
}

int main() {
  int n,k;
  S2(n,k);
  rep(i,0,k) {
    int x;
    S(x);
    X[x] = 1;
  }
  rep(i,n,100000) {
    if(isGood(i)) {
      P(i);
      return 0;
    }
  }
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll n,q,c,up,low,t,x,y,a,b;
double ff;
string str;
vector<string>veca[1000000];
set<ll>seta;
bool f,arr[1000000];

int main()
{
    cin >> a >> b;
    while (b--)
    {
        cin >> x >> str;
        if (str=="AC")
        {
            arr[x]=true;
            seta.insert(x);
        }
        else
        {
            if (arr[x]==false)
            {
                veca[x].push_back(str);
                c++;
            }
        }
    }
    cout << seta.size() << " ";
    for (ll i=1; i<=a; i++)
    {
        if ((arr[i]==false)&&(veca[i].size()>0))
            c-=veca[i].size();
    }
    cout << c << endl;
}


Measured memory_bytes: 30464
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n,m,ans;
  cin >> n >> m;
  vector<int> H(n),A(n,1);
  for(int &e:H)cin >> e;
  for(int i=0;i<m;i++){
    int a,b;
    cin >> a >> b;
    if(H[a-1]<=H[b-1])A[a-1]=0; 
    if(H[b-1]<=H[a-1])A[b-1]=0;
  }
 ans = accumulate(A.begin(),A.end(),0);
  cout << ans << endl;
      return 0;
}


Measured memory_bytes: 4052
#include <bits/stdc++.h>
// statics
using namespace std;
using int64 = long long;
using PAIR = pair<int64, int64>;
constexpr int INF = 1 << 30;
constexpr int64 LINF = 1LL << 60;
constexpr int MOD = 1e9 + 7;
constexpr int MAX_N = 3e5 + 1;

// init/input
#define int int64
#define INIT ios::sync_with_stdio(false);cin.tie(0);
#define VAR(type, ...) type __VA_ARGS__;MACRO_VAR_Scan(__VA_ARGS__);
template<typename T> void MACRO_VAR_Scan(T &t) {cin>>t;}
template<typename First, typename...Rest> void MACRO_VAR_Scan(First &first, Rest&...rest) {cin>>first;MACRO_VAR_Scan(rest...);}
#define VEC(type, c, n) vector<type> c(n);for(auto &&i:c)cin>>i;

// out
#define OUT(dist) cout<<(dist);
#define FOUT(n, dist) cout<<fixed<<setprecision(n)<<(dist);
#define SP cout<<" ";
#define BR cout<<endl;
#define zero(n) cout<<setfill('0')<<right<<setw(n)
#define debug(x) cerr<<#x<<":"<< (x);BR;

// utility
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define EACH(i, a) for(auto &&i:(a))
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define RFOR(i, a, b) for(int i=(b)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<(n);++i)
#define RREP(i, n) for(int i=(n)-1;i>=0;--i)
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; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}

int dp[MAX_N][2];
// j 0->確定,1->未確定

signed main() {
  INIT;
  VAR(string, l);
  int n = l.size();

  dp[0][1] = 1;
  REP(i,n) {

    if (l[i]=='0') {
      (dp[i+1][0] += dp[i][0] * 3) %= MOD;
      (dp[i+1][1] += dp[i][1]) %= MOD;
    } else {
      (dp[i+1][0] += dp[i][0] * 3) %= MOD;
      (dp[i+1][0] += dp[i][1]) %= MOD;
      (dp[i+1][1] += dp[i][1] * 2) %= MOD;
    }
  }

  OUT((dp[n][0]+dp[n][1]) % MOD)BR;
  
  return 0;
}


Measured memory_bytes: 2000
#include <bits/stdc++.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(){
    int x; cin >> x;

    int cmp = 0;
    int id = 1;
    while(cmp+id < x){
        cmp += id;
        id++;
    }

    cout << id << endl;
}

Measured memory_bytes: 256
#define N 100001 
long p[N],r[N],n,m,i,b[N],a[N][2],c,d;int f(int x){if(p[x]==x)return x;return p[x]=f(p[x]);}int u(int x,int y){x=f(x);y=f(y);p[x]=y;r[y]+=r[x];r[x]=r[y];}int main(){scanf("%ld%ld",&n,&m);for(i=0;i<m;i++)scanf("%d%d",a[i],&a[i][1]);b[m]=n*(n-1)/2;for(i=0;i<N;i++){p[i]=i;r[i]=1;};for(i=m-1;i>0;i--){c=a[i][0],d=a[i][1];b[i]=b[i+1];if(f(c)!=f(d)){b[i]=b[i+1]-r[f(c)]*r[f(d)];u(c,d);}}for(i=1;i<=m;i++)printf("%ld\n",b[i]);}

Measured memory_bytes: 5120
#include <iostream>

using namespace std;

int main(){

    int h,w;
    
    while(1){
        cin >> h >> w;
    
        if(h==0 && w==0)break;
        
        for(int i=0; i < h; i++){
            for(int j=0; j < w; j++){
                if((i+j)%2)
                    cout <<".";
                else
                    cout <<"#";
            }
            cout <<endl;
        }
        
        cout <<endl;
    }
    
    return 0;    
}


Measured memory_bytes: 3100
main = do
  [h, w] <- (map read) . words <$> getLine :: IO [Int]
  print $
    if w == 1 || h == 1
       then 1
    else
      if w `mod` 2 == 0
        then w`div`2 * h
      else
        if h `mod` 2 == 0
          then ((w`div`2)+1)*(h`div`2) + (w`div`2)*(h`div`2)
          else ((w`div`2)+1)*((h`div`2)+1) + (w`div`2)*(h`div`2)

Measured memory_bytes: 508
import core.bitop;
import std.algorithm;
import std.ascii;
import std.bigint;
import std.conv;
import std.functional;
import std.math;
import std.numeric;
import std.range;
import std.stdio;
import std.string;
import std.random;

T lread(T = long)()
{
    return readln.chomp.to!T();
}

T[] aryread(T = long)()
{
    return readln.split.to!(T[])();
}

alias sread = () => readln.chomp();

void main()
{
    long A = lread();
    long B = lread();
    long C = lread();
    long X = lread();

    long i;
    foreach (a; 0 .. A + 1)
        foreach (b; 0 .. B + 1)
            foreach (c; 0 .. C + 1)
                if ((a * 500 + b * 100 + c * 50) == X)
                {
                    i++;
                }
    i.writeln();
}


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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,a,b) for(int i=(a);i<(b);i++)
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second

using vint=vector<int>;
using pint=pair<int,int>;
using vpint=vector<pint>;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

template<class A,class B>
ostream& operator<<(ostream& ost,const pair<A,B>&p){
	ost<<"{"<<p.first<<","<<p.second<<"}";
	return ost;
}

template<class T>
ostream& operator<<(ostream& ost,const vector<T>&v){
	ost<<"{";
	for(int i=0;i<v.size();i++){
		if(i)ost<<",";
		ost<<v[i];
	}
	ost<<"}";
	return ost;
}

template<uint32_t mod>
struct ModInt{
	uint32_t a;
	ModInt& s(uint32_t vv){
		a=vv<mod?vv:vv-mod;
		return *this;
	}

	ModInt(int64_t x=0){s(x%mod+mod);}

	ModInt& operator+=(const ModInt &x){return s(a+x.a);}
	ModInt& operator-=(const ModInt &x){return s(a+mod-x.a);}
	ModInt& operator*=(const ModInt &x){
		a=uint64_t(a)*x.a%mod;
		return *this;
	}
	ModInt& operator/=(const ModInt &x){
		*this*=x.inv();
		return *this;
	}

	ModInt operator+(const ModInt &x)const{return ModInt(*this)+=x;}
	ModInt operator-(const ModInt &x)const{return ModInt(*this)-=x;}
	ModInt operator*(const ModInt &x)const{return ModInt(*this)*=x;}
	ModInt operator/(const ModInt &x)const{return ModInt(*this)/=x;}
	bool operator==(const ModInt &x)const{return a==x.a;}
	bool operator!=(const ModInt &x)const{return a!=x.a;}
	bool operator<(const ModInt &x)const{return a<x.a;}

	ModInt operator-()const{return ModInt()-*this;}
	ModInt pow(int64_t n)const{
		ModInt res(1),x(*this);
		while(n){
			if(n&1)res*=x;
			x*=x;
			n>>=1;
		}
		return res;
	}

	ModInt inv()const{return pow(mod-2);}
};

template<uint32_t mod>
istream& operator>>(istream& in,ModInt<mod>& a){
	return (in>>a.a);
}
template<uint32_t mod>
ostream& operator<<(ostream& out,const ModInt<mod>& a){
	return (out<<a.a);
}
using mint=ModInt<1000000007>;
//using mint=ModInt<998244353>;

int N,K;
mint dp[55][55][55*55];
signed main(){
	cin>>N>>K;
	dp[0][0][0]=1;
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			for(int k=0;k<55*55;k++){
				if(dp[i][j][k]==0)continue;
				dp[i+1][j+1][k+(N-i)*2]+=dp[i][j][k];
				dp[i+1][j][k+(N-i)+(i-N)]+=dp[i][j][k]*j;
				dp[i+1][j][k+(N-i)+(i-N)]+=dp[i][j][k]*j;
				if(j)dp[i+1][j-1][k+(i-N)+(i-N)]+=dp[i][j][k]*j*j;
				dp[i+1][j][k]+=dp[i][j][k];
			}
		}
	}

	cout<<dp[N][0][K]<<endl;
	return 0;
}

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

using namespace std;

#define int long long
#define sz(a) (int) (a).size()

const int p = 1e9 + 7;
const int maxn = 1e6 + 10;

int dp[maxn];
int ans = 0, sum = 0;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int n;
    cin >> n;
    dp[1] = 1;
    sum = 0;
    for (int i = 2; i <= n; i++) {
        if (i - 3 >= 0) {
            sum += dp[i - 3];
            sum %= p;
        }
        dp[i] = sum;
        dp[i] += dp[i - 1];
        dp[i] %= p;
//        cout << dp[i] << " ";
    }
//    cout << "\n";
    ans += dp[n] * n % p;
    ans %= p;
    for (int i = 1; i <= n - 1; i++) {
        ans += dp[i] * ((n - 1) * (n - 1) % p) % p;
        ans %= p;
    }
    for (int i = 1; i <= n - 1; i++) {
        ans += dp[i] * min(i + 1, n - 1) % p;
        ans %= p;
    }
    cout << ans << "\n";

    return 0;
}


Measured memory_bytes: 8064
#include <iostream>
using namespace std;
int main()
{
	int A=0, B=0, C=0, D=0;
	cin >> A >> B >> C >> D;
	if (B<=C || A>=D)
	{
		cout << "0";
	}
	else if (A <= C&&B >= D)
	{
		cout << D - C;
	}
	else if (A>=C&&B<=D)
	{
		cout << B - A;
	}
	else if (A <= C&&B <= D)
	{
		if (B > C)
			cout << B - C;
	}
	else if (A >=C&&B >=D)
	{
		if (A < D)
			cout << D - A;
	}
	cout << "\n";
	return 0;
}

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

using namespace std;

int main(){
	int M = 0;
    int sum = 0;
	int N;
	int L[10];
	cin >> N;
	for(int i=0; i<N; i++){
		cin >> L[i];
	}
	for(int i=0; i<N; i++){
		sum += L[i];
	}
	for(int j=0; j<N; j++){
		if(L[j]>M){
			M = L[j];
		}
	}
	if(M*2<sum){
		cout << "Yes" << endl;
	}
	else{
		cout << "No" << endl;
	}

return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("O3")
#pragma GCC target("avx")

#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <utility>

template <const unsigned int N>
struct FastInput{
    char Input[N];
    char* input;
    FastInput(void):Input(), input(Input){ fread_unlocked(Input, sizeof(char), N, stdin); }
    inline int getint(void){
        int res = 0, c; while((c = *(input++) - '0') >= 0) res = 10 * res + c;
        return res;
    }
};

constexpr unsigned int MAX_INPUT = 7400'000;
FastInput<MAX_INPUT> Input;

template <const unsigned int N>
struct FastOutput{
    char Output[N];
    char S[10];
    char* ptr;
    FastOutput(void):Output(), ptr(Output){}
    ~FastOutput(void){ fwrite_unlocked(Output, sizeof(char), ptr - Output, stdout); }
    inline void write(int x){
        if(!x) *(ptr++) = '0';
        else{
            char* p = S;
            while(x){ *p++ = '0' + (x % 10); x /= 10; }
            while(p != S) *ptr++ = *(--p); 
        }
        *(ptr++) = '\n';
    }
};
constexpr unsigned int MAX_OUTPUT = 2400'100;
FastOutput<MAX_OUTPUT> Output;

constexpr unsigned int MAX_N = 200'000;
int A[MAX_N];
int Lis[MAX_N + 1];

struct edge{
    int to; 
    edge* next;
};

edge Edge[2 * MAX_N + 1];
edge* begin[MAX_N];
edge* e_ptr = Edge;
inline void append(const int u, const int v){
    e_ptr -> to = v;
    e_ptr -> next = begin[u];
    begin[u] = e_ptr++;
}

int Ans[MAX_N];
bool visited[MAX_N];

struct stack_type{
    int vertex;
    int val;
};
stack_type Stack[2 * MAX_N + 1];
stack_type * stack = Stack;
inline stack_type* pop(void){ return --stack; }
inline void push(const int v, const int value){ stack -> vertex = v, stack -> val = value; ++stack;}
inline bool empty(void){ return stack == Stack; }

struct Index{
    int index;
    int val;
};
Index Restore[MAX_N];

int main(void){
    int n = Input.getint();
    for(int i = 0; i < n; ++i) A[i] = Input.getint();
    Lis[0] = 0; std::memset(Lis + 1, 0x7f, sizeof(Lis + 1));
    for(int i = 1; i < n; ++i){
        int u = Input.getint() - 1, v = Input.getint() - 1;
        append(u, v); append(v, u);
    }
    visited[0] = true; push(0, 0);
    while(!empty()){
        const stack_type* p = pop();
        const int v = p ->vertex, value = p -> val;
        if(value == -1){ Lis[Restore[v].index] = Restore[v].val; }
        else{
            if(Lis[value] < A[v]){
                Restore[v].index = value + 1; Restore[v].val = INT32_MAX;
                Lis[value + 1] = A[v]; Ans[v] = value + 1;
            }
            else{
                int ok = 0, ng = value;
                while(ng - ok > 1){
                    const int mid = (ok + ng) >> 1;
                    if(Lis[mid] < A[v]) ok = mid; else ng = mid;
                }
                Restore[v].index = ng; Restore[v].val = Lis[ng];
                Lis[ng] = A[v]; Ans[v] = value;
            }
            push(v, -1);
            for(edge* itr = begin[v]; itr; itr = itr -> next) if(!visited[itr -> to]){ 
                visited[itr -> to] = true; push(itr -> to, Ans[v]);
            }
        }
    }

    for(int i = 0; i < n; ++i) Output.write(Ans[i]);
    return 0;
}


Measured memory_bytes: 25024
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
  char c;
  cin >> c;
  if (c == 'a' || c == 'i' || c == 'u' || c == 'e' || c == 'o') {
    cout << "vowel" << endl;
  } else {
    cout << "consonant" << endl;
  }
}

Measured memory_bytes: 256