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

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            new Program().Solve(new ConsoleInput(Console.In, ' '));
#if DEBUG
            ReadLine();
#endif
        }

        void Solve(ConsoleInput cin)
        {
            int m = cin.ReadInt;
            int d = cin.ReadInt;

            int ans = 0;

            for (int i = 1; i <= m; i++)
            {
                for (int j = 10; j <= d; j++)
                {
                    int d_10 = j / 10;
                    int d_1 = j - d_10 * 10;

                    if (d_1 < 2 || d_10 < 2)
                    {
                        continue;
                    }

                    if (i == d_1 * d_10)
                    {
                        ans++;
                    }
                }
            }

            WriteLine(ans);
        }

        class ConsoleInput
        {
            private readonly System.IO.TextReader _stream;
            private char _separator = ' ';
            private Queue<string> inputStream;

            public ConsoleInput(System.IO.TextReader stream, char separator = ' ')
            {
                this._separator = separator;
                this._stream = stream;
                inputStream = new Queue<string>();
            }

            public string Read
            {
                get
                {
                    if (inputStream.Count != 0) return inputStream.Dequeue();
                    string[] tmp = _stream.ReadLine().Split(_separator);
                    for (int i = 0; i < tmp.Length; ++i)
                        inputStream.Enqueue(tmp[i]);
                    return inputStream.Dequeue();
                }
            }

            public string ReadLine { get { return _stream.ReadLine(); } }
            public int ReadInt { get { return int.Parse(Read); } }
            public long ReadLong { get { return long.Parse(Read); } }
            public double ReadDouble { get { return double.Parse(Read); } }
            public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret; }
            public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret; }
            public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret; }
        }
    }
}

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

using namespace std;

#define INF 1145141919

int main(void){
  int N,i,ans=0;
  cin >> N;
  int A[N],dp[N];
  for(i=N-1;i>=0;i--){
    cin >> A[i];
  }
  fill(dp,dp+N,INF);
  for(i=0;i<N;i++){
    *upper_bound(dp,dp+N,A[i])=A[i];
  }
  ans=lower_bound(dp,dp+N,INF)-dp;
  cout << ans << endl;
}

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

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

int main(){
  ll n; cin >> n;
  vector<pair<ll,ll>> v;
  rep(i,n){
    ll a,b;
    cin >> a >> b;
    v.push_back(make_pair(b,a));
  }
  sort(v.begin(),v.end());
  ll sum = 0;
  rep(i,n){
    ll b = v[i].first;
    ll a = v[i].second;
    sum += a;
    if(sum>b){
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
  return 0;
}

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

int H, W;
char C[100][100];

char C2[200][100];

int main() {
    cin >> H >> W;
    rep(i, H)rep(j, W) cin >> C[i][j];

    // rep(i, H) {
    //     rep(j, W) {
    //         cout << C[i][j];
    //     }
    //     cout << endl;
    // }

    rep(i, 2 * H)rep(j, W) {
        // printf("i: %d, j: %d C: %c\n", i, j, C[i / 2][j]);
        C2[i][j] = C[i / 2][j];
    }

    rep(i, 2 * H) {
        rep(j, W) {
            cout << C2[i][j];
        }
        cout << endl;
    }
}

Measured memory_bytes: 256
//  ALDS1-ALDS1_7_A  Tree - Rooted Trees
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;

const int MAX = 100005;
const int NIL = -1;

struct Node
{
	int parent = NIL;
	int left = NIL;
	int right = NIL;
};

Node T[MAX];
int n, D[MAX];

int getDepth(int u)
{
	int depth = 0;
	while (T[u].parent != NIL)
	{
		u = T[u].parent;
		depth++;
	}
	return depth;
}

void rec(int u, int p)
{
	D[u] = p;
	if (T[u].right != NIL ) rec(T[u].right, p); //右の兄弟に同じ深さを設定
	if (T[u].left != NIL ) rec(T[u].left, p+1); //もっとも左の子に自分の深さ＋1を設定
}

string getType(int u)
{
	if (T[u].parent == NIL ) return "root";
	else if (T[u].left == NIL) return "leaf";
	else return "internal node";
}

string getClidren(int u)
{
	string str = "[";
	if(T[u].left!=NIL)
	{
		int node = T[u].left;
		str += to_string(node);
		while (T[node].right != NIL)
		{
			node = T[node].right;
			str += ", " + to_string(node);
		}
	}
	str += "]";

	return str;
}

void printNodeStructs()
{
	for (int i = 0; i < n; i++)
	{
		printf("node %d p=%2d ,l=%2d, r=%2d, d=%2d, dr=%d,type=%s,%s\n",
		i,T[i].parent,T[i].left,T[i].right,getDepth(i),D[i],getType(i).c_str(),getClidren(i).c_str());
	}
}

void print()
{
	for (int i = 0; i < n; i++)
	{
		printf("node %d: parent = %d, depth = %d, %s, %s\n",
		i,T[i].parent,D[i],getType(i).c_str(),getClidren(i).c_str());
	}
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int vertex,depth, c, l;
		cin >> vertex >> depth;
		for (int j = 0; j < depth; j++)
		{
			cin >> c;
			if (j == 0)
			{
				T[vertex].left = c;
			}
			else
			{
				T[l].right = c;
			}
			l = c;
			T[c].parent = vertex;
		}
	}

	int r;
	for (int i = 0; i < n; i++)
	{
		if(T[i].parent == NIL ) {
			r = i;
		}
	}
	rec(r,0);
	
	//printNodeStructs();
	print();
	return 0;
}


Measured memory_bytes: 8552
#include <cstdio>
using namespace std;
int main(){
	int n;
	scanf("%d",&n);
	n%=10;
	if(n==2||n==4||n==5||n==7||n==9)printf("hon\n");
	if(n==0||n==1||n==6||n==8)printf("pon\n");
	if(n==3)printf("bon\n");
	return 0;
}


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

#define ll long long
#define sd(x) scanf("%d", &(x))
#define pii pair<int, int>
#define F first
#define S second


const int mod = 1e9 + 7;
inline int add(int x, int y){ x += y; if(x >= mod) x -= mod; return x;}
inline int sub(int x, int y){ x -= y; if(x < 0) x += mod; return x;}
inline int mul(int x, int y){ return (((ll) x) * y) % mod;}
inline int powr(int a, ll b){
	int x = 1 % mod;
	while(b){
		if(b & 1) x = mul(x, a);
		a = mul(a, a);
		b >>= 1;
	}
	return x;
}
inline int inv(int a){ return powr(a, mod - 2);}

const int N = 2e5 + 10;
int dp[N], dp2[N];
int c[N];
int main(){
	int n; sd(n);
	for(int i = 1; i <= n; i++) sd(c[i]);
	dp[n + 1] = dp2[c[n]] = 1;
	for(int i = n; i >= 1; i--){
		if(i == 1 || c[i] != c[i - 1]){
			dp[i] = dp2[c[i]];
			dp2[c[i - 1]] = add(dp2[c[i - 1]], dp[i]);
		}
	}
	printf("%d\n", dp[1]);
}

Measured memory_bytes: 2560
import sys

input = sys.stdin.readline
n, m = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(m)]
BC.sort(key=lambda x: -x[1])

maxi = n*2
extend = A.extend
[extend([ls[1]] * ls[0]) for ls in BC if len(A) <= maxi]
A.sort(reverse=True)

print(sum(A[:n]))

Measured memory_bytes: 36088
from collections import deque
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
write = sys.stdout.write
def solve():
    N = int(readline())
    G = [[] for i in range(N)]
    for i in range(N):
        *vs, = readline()
        for j in range(N):
            if vs[j] == "Y":
                G[i].append(j)
    d = 0
    C = [0, 0]
    used = [0]*N
    for i in range(N):
        d += len(G[i])
        if used[i]:
            continue
        used[i] = 1
        que = deque([i])
        c = 0
        while que:
            v = que.popleft()
            c += 1
            for w in G[v]:
                if used[w]:
                    continue
                used[w] = 1
                que.append(w)
        C[c % 2] += 1
    r0 = (N*(N-1)//2 - d//2) & 1
    memo = {}
    def dfs(i, p, q):
        key = (p, q)
        if key in memo:
            return memo[key]
        if p+q == 2:
            r = (q == 2) ^ r0
            memo[key] = e = r ^ (i & 1)
            return e
        r = 0
        if p > 1 or (p and q):
            if dfs(i+1, p-1, q) == 0:
                r = 1
        if q > 1:
            if dfs(i+1, p+1, q-2) == 0:
                r = 1
        memo[key] = r
        return r
    if dfs(0, C[0], C[1]):
        write("Taro\n")
    else:
        write("Hanako\n")
solve()



Measured memory_bytes: 23432
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using P = pair<ll,ll>;
const ll mod = 1e9+7;
#define ALL(x) (x).begin(),(x).end()
#define pow(x,y) modpow(x,y)
#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)

template <class T = int>T in(){
    T x;
    cin >> x;
    return (x);
}

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(10);
    char a = in<char>(),b = in<char>();
    cout << (a == b ? 'H' : 'D') << "\n";
}

Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG

#include<bits/stdc++.h>
#define PI 3.14159265359
using namespace std;
const int INF= 1e9+5;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>>vvi;

int main(){
  int a,b,c,d;
  cin>>a>>b>>c>>d;
  int ans=min(b,d)-max(a,c);
  if(ans<0)cout<<0<<endl;
  else cout<<ans<<endl;
}

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

int main() {
    int A, B, C, X;
    cin >> A >> B >> C >> X;
    int counter = 0;
    for (int i=0; i<=A; i++) {
        for (int j=0; j<=B; j++) {
            for (int k=0; k<=C; k++) {
                if (500*i + 100*j + 50*k == X) counter++;
            }
        }
    }
    cout << counter << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using PII = pair<int, int>;
#define FI(i,a,b) for(int i=(a);i<=(b);++i)
#define FD(i,b,a) for(int i=(b);i>=(a);--i)
#define DEBUG(x) cerr << #x << ": " << (x) << endl;
constexpr LL inv(LL x, LL m) { return x > m ? inv(x % m, m) : x > 1 ? inv(m % x, m) * (m - m / x) % m : x; }
constexpr LL mpow(LL a, LL k, LL m) { LL r(1); for (a %= m; k; k >>= 1, a = a * a % m) if (k & 1)r = r * a % m; return r; }

const int N = 1e5 + 5;
int n, x;

int main() {
    scanf("%d", &n);
    bool flag = false;
    FI(i, 1, n) {
        scanf("%d", &x);
        if (x & 1) flag = true;
    }
    printf(flag ? "first\n" : "second\n");
}


Measured memory_bytes: 256
def f(yen, coin, cnt=0):
    while yen > 0: cnt += yen % coin; yen //= coin
    return cnt

ans = n = int(input())
for yen6 in range(0, n+1):
    ans = min(ans, f(n-yen6, 9, f(yen6, 6)))
print(ans)


Measured memory_bytes: 2940
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
    S = input()
    w = int(input())
    ans = []
    for i in range(0,len(S),w):
        ans.append(S[i])
    print(''.join(ans))
if __name__ == '__main__':
    main()

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

using namespace std;
using vecint = vector<int>;
using ll = int64_t;

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


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

const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define ALL(v) (v.begin(),v.end())
#define COUT(x) cout<<(x)<<endl

int main(){
    int n;
    cin >> n;
    int b[n-1];
    REP(i,n-1){
        cin >> b[i]; 
    }
    int ans = b[0]+b[n-2];
    FOR(i,1,n-1){
        ans += min(b[i],b[i-1]);
    }
    COUT(ans);
    return 0;
}  

Measured memory_bytes: 256
#include <bits/stdc++.h> 
using namespace std;
#define rep(i, N) for(int i=0; i<N; i++)
typedef long long ll;
#define dump(x) cerr<<#x<<"="<<x<<endl

int main() {
    string s; cin >> s;
    
    auto ok = [](string S){
        bool tmp = true;
        for(int i=0; i<S.size()/2; i++){
            if(S.at(i)==S.at(i+S.size()/2)) continue;
            else tmp = false;
        }

        return tmp;
    };

    ll res = 0;
    string t;
    rep(i, s.size()-2) t += s.at(i);
    res += 2;
    while(!ok(t)){
        res += 2;
        t = "";
        rep(i, s.size()-res) t += s.at(i);
    }

    cout << s.size() - res << endl;

    dump(t);
}

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

int main() {

  int n;
  cin >> n;

  int c[n][26];

  for(int i = 0;i < n;i++) {
    for(int j = 0;j < 26;j++) {
      c[i][j] = 0;
    }
  }

  for(int i = 0;i < n;i++) {
    string S;
    cin >> S;
    for(int j = 0;j < S.size();j++) {
      int k = S.at(j) - 'a';
      c[i][k]++;
    }
  }

  string ans;
  for(int i = 0;i < 26;i++) {
    int mini = 100;
    for(int j = 0;j < n;j++) {
      mini = min(mini,c[j][i]);
    }

    for(int k = 0;k < mini;k++) {
      ans.push_back((char)(i + 'a'));
    }
  }

  cout << ans << endl;
  
}




Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
using std::swap;

void J(char s[], int len){
    char tmp = s[len-1];
    for(int i=len-1;i>0;i--){
        s[i] = s[i-1];
    }s[0] = tmp;
}
void C(char s[], int len){
    char tmp = s[0];
    for(int i=0;i<len-1;i++){
        s[i] = s[i+1];
    }s[len-1] = tmp;
}
void E(char s[], int len){
    int mid = len/2;
    for(int i=0;i<mid;i++){
        swap(s[i], s[len-mid+i]);
    }
}
void A(char s[], int len){
    char tmp = s[len-1];
    for(int i=0;i<len-1-i;i++){
        swap(s[i], s[len-1-i]);
    }
}
void P(char s[], int len){
    for(int i=0;i<len;i++){
        if('0'<=s[i] && s[i]<='9'){
            s[i] = '0'+(s[i]-'0'+9)%10;
        }
    }
}
void M(char s[], int len){
    for(int i=0;i<len;i++){
        if('0'<=s[i] && s[i]<='9'){
            s[i] = '0'+(s[i]-'0'+1)%10;
        }
    }
}

int main(){
    int N;
    scanf("%d", &N);
    while(N--){
        char s1[50], s2[50];
        scanf("%s %s", s1, s2);
        int len1;
        for(len1=0 ; s1[len1]!='\0' ; len1++);
        int len2;
        for(len2=0 ; s2[len2]!='\0' ; len2++);
        
        for(int i=len1-1;i>=0;i--){
            if(s1[i] == 'J') J(s2, len2);
            if(s1[i] == 'C') C(s2, len2);
            if(s1[i] == 'E') E(s2, len2);
            if(s1[i] == 'A') A(s2, len2);
            if(s1[i] == 'P') P(s2, len2);
            if(s1[i] == 'M') M(s2, len2);
        }
        printf("%s\n", s2);
    }
    return 0;
}

Measured memory_bytes: 1008
#include <bits/stdc++.h>
#include <string>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

int my_abs(int num){
   if (num > 0)
      return num;
   else
      return -num;
}

int main(){
    int N,K;
    cin >> N >> K;
    vector<int> stick(N);
    for(int i = 0;i<N;i++){
        cin >> stick.at(i);
    }
    sort(stick.begin(),stick.end());
    reverse(stick.begin(),stick.end());
    int ans = 0;
    for(int j = 0;j<K;j++){
        ans = ans + stick.at(j);
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
N = int(input())
a = [int(i) for i in input().split()]
Min = min(a)-1
Max = max(a)+1
ans = [0 for i in range(Min, Max+1)]

for i in a:
    ans[i-Min-1] += 1
    ans[i-Min] += 1
    ans[i-Min+1] += 1
        
print(max(ans))
        


Measured memory_bytes: 13964
package main

import (
        "bufio"
        "bytes"
        "fmt"
        "io"
        "os"
        "strconv"
        "strings"
)

func main() {
        fmt.Println(run(os.Stdin))
}

func run(in io.Reader) string {
        sc := bufio.NewScanner(in)

        sc.Scan()
        n, err := strconv.Atoi(sc.Text())
        if err != nil {
                panic(err)
        }

        sc.Scan()
        arrs := strings.Split(sc.Text(), " ")
        arr := make([]int, n)
        for i, v := range arrs {
                if arr[i], err = strconv.Atoi(v); err != nil {
                        panic(err)
                }
        }

        return bubbleSort(n, arr)
}

func bubbleSort(n int, arr []int) string {
        buf := new(bytes.Buffer)

        cnt := 0

        flag := true

        for flag {
                flag = false
                for i := n - 1; i > 0; i-- {
                        if arr[i] < arr[i-1] {
                                swap(arr, i, i-1)
                                cnt++
                                flag = true
                        }
                }
        }

        for i, v := range arr {
                if i > 0 {
                        fmt.Fprintf(buf, " ")
                }
                fmt.Fprintf(buf, "%d", v)
        }
        fmt.Fprintf(buf, "\n%d", cnt)

        return buf.String()
}

func swap(arr []int, i, j int) {
        arr[i], arr[j] = arr[j], arr[i]
}



Measured memory_bytes: 1176
#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
#include <algorithm>
#include <limits.h>
using namespace std; 
int main(int argc,char const* argv[])
{
  int n;
  long long c,k;
  cin >> n >> c >> k;
  int person=0,time=0;
  vector<long long>t(n,0);
  long long answer=0;
  for(int i=0;i<n;i++)
    {
      cin >> t[i];
    }
  sort(t.begin(),t.end());
  for(int i=0;i<n;i++)
    {
      if(c <=person || time<t[i])
	{
	  answer++;
	  time=t[i]+k;
	  person=0;
	}
      person++;
    }
  cout << answer << endl;
  return 0;
}


Measured memory_bytes: 1152
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
using namespace std;
typedef double D;
typedef complex<D> P;
const D EPS = 1e-8;
const D PI = acos(-1);

int n,r,q,r2;
P p[30];
int cur;
D min_s[30],x,y;

inline D dot(const P &x, const P &y){return real(conj(x)*y);}

inline P rotate(const P &v, const D &s){
  return P(real(v)*cos(s) - imag(v)*sin(s), real(v)*sin(s) + imag(v)*cos(s) );
}

inline D arg(const P &a,const P &b,const P &c){return dot(b-a,c-a)/(abs(b-a)*abs(c-a));}

inline D rot_seta(const int &end){
  D dis = norm(p[end]-p[cur]);
  D seta = acos( (r2 - dis)/(r2) );
  P nxt = rotate(p[cur],-seta);
  return arg(p[cur],p[end],nxt);
}

int main(){
  while(scanf("%d%d%d",&n,&r,&q), n){
    r2 = 2*r*r;
    rep(i,n){
      scanf("%lf%lf",&x,&y);
      p[i] = P(x,y);
      if(abs(abs(p[i])-r)<EPS)cur = i;
    }
    
    vector<int> nxt(n,-1);

    rep(i,q){
      if(nxt[cur]<0){
	min_s[cur] = PI;
	rep(j,n){
	  if(cur==j)continue;
	  D s = rot_seta(j);
	  if(nxt[cur]<0 || s > min_s[cur]+EPS)nxt[cur] = j, min_s[cur] = s;
	}
	min_s[cur] = acos(min_s[cur]);
      }

      rep(j,n){
	if(j==cur)continue;
	p[j] = rotate(p[j]-p[cur],min_s[cur]) + p[cur];
      }
      printf("%.9lf %.9lf\n",p[nxt[cur]].real(), p[nxt[cur]].imag());

      if(i==0){
	int tmp = nxt[cur];
	nxt[cur] = -1;
	cur = tmp;
      }else{
	cur = nxt[cur];
      }
    }
  }
}

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

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

  int s[n];
  int res = 0;
  bool tf = false;
  int not10 = 0;
  for(int i=0;i<n;++i)
    cin >> s[i];

  sort(s,s+n);

  for(int i=0;i<n;++i)
  {
    res += s[i];
    if(tf == false && s[i]%10 != 0)
    {
      not10 = s[i];
      tf = true;
    }
  }

  if(res%10 == 0)
  {
    if(tf == true) res -= not10;
    else res = 0;
  }

  cout << res << endl;
}

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

#define _USE_MATH_DEFINES
#include<cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iterator>
#include<iomanip>
#include<unordered_set>
#include<bitset>
#include<complex>

using namespace std;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

#define int ll
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

//typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;
typedef vector< vector<int> > mat;

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

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;

int N, M;
int A[100010];
int SUM[100010];

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

	cin >> N >> M;
	rep(i, 0, N)
	{
		cin >> A[i];
	}

	sort(A, A + N);

	rep(i, 0, N)
	{
		SUM[i + 1] = A[i];
		SUM[i + 1] += SUM[i];
	}

	int l = 0, r = 200010;
	while (r - l > 1)
	{
		int mid = (l + r) / 2;
		int cnt = 0;
		rep(i, 0, N)
		{
			int ind = lower_bound(A, A + N, mid - A[i]) - A;
			cnt += (N - ind);
		}
		if (cnt < M)
		{
			r = mid;
		}
		else
		{
			l = mid;
		}
	}

	int ans = 0;
	int cnt = 0;
	rep(i, 0, N)
	{
		int ind = lower_bound(A, A + N, l - A[i]) - A;
		ans += (N - ind)*A[i] + SUM[N] - SUM[ind];
		cnt += (N - ind);
	}

	ans -= (cnt - M)*l;
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <string>
#include <tuple>
#include <algorithm>
#include <numeric>
#include <climits>

using namespace std;

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

    long ans;
    int r = n % 11;
    if (r == 0) {
        ans = n/11 * 2;
    } else if (r <= 6) {
        ans = n/11 * 2 + 1;
    } else {
        ans = n/11 * 2 + 2;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
import sys
import os
import math
import string

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: x * y / math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A = il()
    print(max(A)-min(A))


if __name__ == '__main__':
    main()


Measured memory_bytes: 3832
#include <bits/stdc++.h>
#define sp ' '
#define nyan "(=^・ω・^=)"
#define mkp make_pair
#define intmax 2147483647
#define llmax 9223372036854775807
#define lP pair<ll,ll>
#define iP pair<int,int>
typedef long long ll;
using namespace std;
const int mod = 1000000007;

int a[100000], l, r, t, tree[262144];
ll N;
iP p[100001];

int calc(int x) {
	x += 131072;
	int a = 0;
	while (x) {
		a += tree[x];
		x /= 2;
	}
	return a;
}
void update(int l, int r, int k, int p, int q) {
	if (!(q < l || r < p)) {
		if (p <= l && r <= q)
			++tree[k];
		else {
			update(l, (l + r) / 2, k * 2, p, q);
			update((l + r) / 2 + 1, r, k * 2 + 1, p, q);
		}
	}
}

int main() {
	cin >> N;
	for (int i = 0; i != N; ++i) {
		cin >> a[i];
		r = max(r, a[i]);
	}
	while (l + 1 != r) {
		memset(tree, 0, sizeof tree);
		int k = (l + r) / 2;
		t = 0;
		for (int i = 0; i != N; ++i) {
			p[i] = mkp(t, i);
			if (a[i] > k)
				++t;
			else
				--t;
		}
		p[N] = mkp(t, N);
		sort(p, p + N + 1);
		ll A = 0;
		for (int i = 0; i != N + 1; ++i) {
			A += p[i].second - calc(p[i].second);
			update(0, 131071, 1, p[i].second, N + 1);
		}
		cerr << k << sp << A << endl;
		if (A <= (N*(N - 1) / 2 + N) / 2)
			l = k;
		else
			r = k;
	}
	cout << r << endl;
	return 0;
}

Measured memory_bytes: 2432
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int ans;
  int X;
  cin >> X;
  int A=X%100;
  int B=X/100;
  if(B*5>=A){
    cout << 1 << endl;
  }else{
    cout << 0 << endl;
  }
  
}

Measured memory_bytes: 256
N, M = gets.split.map(&:to_i)
as = gets.split.map(&:to_i)

a_to_count = [2, 5, 5, 4, 5, 6, 3, 7, 6].map.with_index do |n, i|
  [i + 1, n]
end.to_h

match_counts = as.map { |a| a_to_count[a] }.uniq
match_count_a = match_counts.map do |c|
  max_a = as.select { |a| a_to_count[a] == c }.max
  [c, max_a]
end.sort_by { |c, a| -a }

dp = Array.new(N + 1, nil)
dp[0] = [0, Array.new(9, 0)]
(0..N).each do |i|
  count, list = dp[i]
  next unless list
  match_count_a.each do |(c, a)|
    next if i + c > N
    t = list.dup
    t[9 - a] += 1
    if dp[i + c] == nil || ([count + 1, t] <=> dp[i + c]) > 0
      dp[i + c] = [count + 1, t]
    end
  end
end
ans = dp[N][1].each.with_index.reduce('') do |acc, (count, i)|
  a = 9 - i
  acc += a.to_s * count
end
puts ans


Measured memory_bytes: 5116
from collections import Counter


def solve(string):
    s, k = string.split()
    """
    g = []
    for i in range(len(s)):
        for j in range(i + 1, len(s) + 1):
            g.append(s[i:j])
    g = sorted(set(g))
    return g[int(k)-1]
    """
    k = int(k)
    count = Counter(s)
    chars = sorted(set(s))
    for t in range(min(3, len(chars))):
        tmp = []
        i = s.index(chars[t])
        tmp.append(s[i:i + 5])
        if count[chars[t]] > 1:
            for _ in range(count[chars[t]] - 1):
                i = s.index(chars[t], i + 1)
                tmp.append(s[i:i + 5])
        g = []
        for p in tmp:
            for j in range(1, len(p) + 1):
                g.append(p[:j])
        g = sorted(set(g))
        if len(g) < k:
            k -= len(g)
            continue
        return g[k - 1]


if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))


Measured memory_bytes: 41584
#include <iostream>
#include <cassert>
#include <algorithm>
#include <functional>
using namespace std;

int main(){
    long long N, A, B, C, D, E;
    cin >> N >> A >> B >> C >> D >> E;

    long long m;
  m= min( min( min( min(A, B), C), D), E);
//    m=min({A, B, C, D, E});
    long long t = (N+m-1)/m; //一番遅い人がBまでいく時間

    cout << t+4 << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
int main(void){
    int N[3];
    cin >> N[0] >> N[1] >> N[2];
    int K;
    cin >> K;
    sort(N,N+3);
    for(int i = 0;i < K;i++)N[2]*=2;
    cout << N[0] + N[1] + N[2] << endl;
}


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

#define rep(i, n) for (int i = 0; i < (n); i++)
#define contains(v, t) (find(v.begin(), v.end(), t) != v.end())
#define MOD 1000000007
typedef long long ll;
typedef unsigned long long ull;

int main() {
  string s;
  cin >> s;
  int zero = 0, one = 0;
  rep(i, s.length()) {
    if (s[i] == '0') zero++;
    else one++;
  }
  cout << s.length() - (max(zero, one) - min(zero, one)) << endl;
}


Measured memory_bytes: 512
s = input()
if s == 'SUN':
  print(7)
elif s == 'MON':
  print(6)
elif s == 'TUE':
  print(5)
elif s == 'WED':
  print(4)
elif s == 'THU':
  print(3)
elif s == 'FRI':
  print(2)
elif s == 'SAT':
  print(1)
else:
  raise ValueError

Measured memory_bytes: 2940
#include <iostream>
using namespace std;
int main(){
    string str;
    cin >>str;
    bool judge=true;
    for(int i=0;i<str.size();i++){
        for(int j=i+1;j<str.size();j++){
            if(str[i]==str[j])judge=false;
        }
    }
    if(judge)cout<<"yes"<<endl;
    else cout <<"no"<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long long A,B,V,W,T;
int main(){
    cin>>A>>V>>B>>W>>T;
    long long D=V-W;
    if(D<=0){cout<<"NO"<<endl;return 0;}
    if(D*T>=abs(A-B))cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}

Measured memory_bytes: 3632
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
    	Set<Integer> num = new HashSet<>();
        for (int i=0; i<N; i++) {
            int di = sc.nextInt();
            num.add(di);
        }
        System.out.println(num.size());
    }
}

Measured memory_bytes: 23632
#include <bits/stdc++.h>
using namespace std;
int main (){
  int i,n,j=0,mx=0;
  string x;
  int count=0;
  cin>>n;
  vector <string> s(n);
  vector <int> cnt(n),a;
  for(i=0;i<n;i++){
    cin>>s[i];
    cnt[i]=0;
  }
  sort(s.begin(),s.end());
  for(i=0;i<n;i++){
    x = s[i];
    if(i==n-1){
      a.push_back(j);
      mx = max(cnt[j],mx);
      count++;
      j=i+1;
    }
    else if(x == s[i+1]){
      cnt[j]++;
    }
    else
    {
      a.push_back(j);
      mx = max(cnt[j],mx);
      count++;
      j=i+1;
    }
  }
  for(i=0;i<count;i++){
    if(mx == cnt[a[i]]){
      cout<<s[a[i]]<<endl;
    }
    
    
  }
  return 0;
}

Measured memory_bytes: 15992
void main(){
  import std.stdio, std.string, std.conv, std.algorithm;
  
  long n; rd(n);

  for(long a=1; a<=3500; a++)for(long b=1; b<=3500; b++){
    auto x=4*a*b-n*a-n*b;
    if(x<=0) continue;
    auto y=n*a*b;
    if(y%x==0){
      writeln(a, " ", b, " ", y/x); return;
    }
  }

}


void rd(T...)(ref T x){
  import std.stdio, std.string, std.conv;
  auto l=readln.split;
  foreach(i, ref e; x){
    e=l[i].to!(typeof(e));
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const double pi = acos(-1);
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
REP(i,v.size()){if(i)os<<" ";os<<v[i];}return os;}
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) {
REP(i,v.size()){if(i)os<<endl;os<<v[i];}return os;}

int main() {
    // メインプログラムここから
    ll n,l,ans=0;
    vector<ll> v;
    
    cin >> n;
    
    for(int i=0; i<2*n; i++){
        cin >> l;
        v.push_back(l);
    }
    
    sort(v.begin(), v.end());
    
    for(int i=0; i<n; i++){
        ans += v[0];
        v.erase(v.begin());
        v.erase(v.begin());
    }
    
    cout << ans << endl;
    // ここまで
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#define int long long
 
using namespace std;
int plas(int N){
	if(N<0)	return N*-1;
	return N;
}
 
signed main(){
	int K;
	cin >> K;
	int N;	//Nは2以上
	int a[51];
	int NN=0;
	for(int i=0;i<50;i++){
		a[i]=i;
	}
	if(K<=2){
		switch(K){
			case 0:
			cout << "2\n1 1\n";
			break;
			case 1:
			cout << "2\n3 0\n";
			break;
			case 2:
			cout << "2\n2 2\n";
			break;
		}
		return 0;
	}
	if(K<=50){
		cout << K;
		cout << "\n1";
		for(int i=1;i<K;i++){
			cout << " " << i+1;
		}
		cout << endl;
		return 0;
	}
	int NNN;
	NNN = K/50;
	for(int i=0;i<50;i++){
		a[i]+=NNN;
	}
	NN = K-NNN*50;
	//NNを端数にする 0<=NN<50
	for(int i=0;i<NN;i++){
		for(int j=0;j<50;j++){
			if(j==i){
				a[j]+=50;
			}else{
				a[j]--;
			}
		}
	}
	cout << 50 << endl;
	cout << a[0];
	for(int i=1;i<50;i++){
		cout << " " << a[i];
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include <fstream>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>

unsigned gcd(unsigned a, unsigned b) {
  if(a < b) return gcd(b, a);
  unsigned r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}

#define LOCAL  1
#define UPLOAD 2

using namespace std;
typedef long long ll;

template <class T = ll>
T input(){T x;cin >> x;return x;}

template <class T>
void output(T x){cout << x << endl;}

//#define int long log

#define debug(x) cerr << #x<< ": " << x<< '\n';

int main()
{
#if ENVIRONMENT == LOCAL
    std::ifstream in("input.txt");
    std::cin.rdbuf(in.rdbuf());
#endif

  int r = input();
  output(r*r*3);
  
  return 0;
}

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

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}

#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define REP(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define FORD(i, a, b) for(int i = (a); i >= (b); i--)
#define A first
#define B second
#define MOD 1000000007

typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef long long ll;

int mulmd(ll a, ll b){
    ll ret = (a * b) % MOD;
    return (int)ret;
}

inline int power(ll x, ll y, int p)
{
    ll res = 1;
    x = x % p;
    while (y > 0)
    {
        if (y & 1)
            res = mulmd(res, x);
        y = y >> 1;
        x = mulmd(x, x);
    }
    return (int)res;
}

int submd(ll a, ll b){
    ll ret = a - b;
    if(ret < 0){
        ret += MOD;
    }
    return (int)ret;
}

int addmd(ll a, ll b){
    ll ret = (a + b) % MOD;
    return (int)ret;
}

int invPow(ll a){
    return power(a, MOD - 2, MOD);
}

const int N = 1e5 + 5;

int arr[N];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s;
    cin >> s;
    if(s == "Sunny") cout << "Cloudy";
    else if(s == "Cloudy") cout << "Rainy";
    else cout << "Sunny";
}

/**
    Check out for boundary cases, (n = 1 or n = 0)
    check for integer overflow

**/



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
  if((a=a%b)==0)
    return b;
  else
    return gcd(b,a);
}
int main(){
  int K,i,j,k,A=0;
  cin >> K;
  for(i=1;i<=K;i++){
    for(j=i;j<=K;j++){
      for(k=j;k<=K;k++){
        if(k==i)
          A+=k;
        else if(k==j)
          A+=3*gcd(j,i);
        else if(j==i)
          A+=3*gcd(k,j);
        else
          A+=6*gcd(k,gcd(j,i));
      }
    }
  }
    
  cout << A;
}

Measured memory_bytes: 3636
#include<iostream>
#include<iomanip>
#include<math.h>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#define INF 1000000000ll
#define MOD 1000000007ll
#define EPS 1e-10
#define REP(i,m) for(long long i=0; i<m; i++)
#define FOR(i,n,m) for(long long i=n; i<m; i++)
#define DUMP(a) for(long long dump=0; dump<(ll)a.size(); dump++) { cout<<a[dump]; if(dump!=n-1) cout<<" "; else cout<<endl; }
#define ALL(v) v.begin(),v.end()
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef long double ld;

/*
 貪欲
 ?決定問題 必ず解に含まれる(含むように変換できる)ものから決めていく みんプロ本選B
 ?最適化問題 任意の解から評価を落とさず解に含められるようなものから決めていく 区間スケジューリングとか
 ?
 */

/*
 DP
 ?DPはある程度決め打ちをするべき(解を帰納的に構成できないか？)
 */

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n,q;
	cin>>n>>q;
	vector<ll> cnt(n,0);
	priority_queue<P> que;
	REP(i,n) que.push(P(0,-i));
	REP(i,q) {
		ll a,v;
		cin>>a>>v;
		a--;
		cnt[a]+=v;
		que.push(P(cnt[a],-a));
		while(cnt[-que.top().second]!=que.top().first) que.pop();
		cout<<-que.top().second+1<<" "<<que.top().first<<endl;
	}
}

Measured memory_bytes: 43544
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <iomanip>
#include <stack>
#include <queue>
#include <numeric>
#include <map>
#include <unordered_map>
#include <set>
#include <fstream>
#include <chrono>
#include <random>
#include <bitset>
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) ((int)(x).size())
#define pb push_back
#define mod 1000000007
using ll = long long;
using namespace std;
ll gcd(ll a, ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) {return a/gcd(a,b)*b;}

int main(){
  const ll inf = 1e18;
  ll N, M; cin >> N >> M;
  ll S; cin >> S;
  S = min(5000LL, S);
  ll u, v, a, b;
  vector<vector<pair<ll,pair<ll,ll>>>> G(N);
  rep(i,M){
    cin >> u >> v >> a >> b; // pos-pos, money, time
    u--; v--;
    G[u].pb({v,{a,b}});
    G[v].pb({u,{a,b}});
  }
  vector<ll> C(N);
  vector<ll> D(N);
  rep(i,N) cin >> C[i] >> D[i]; // money, time

  vector<vector<ll>> dist(N, vector<ll> (5001, inf));
  dist[0][S] = 0;
  priority_queue<pair<ll, pair<ll,ll>>, vector<pair<ll,pair<ll,ll>>>, greater<pair<ll,pair<ll,ll>>>> q;
  q.push({0,{0,S}}); // time, pos, money
  while(!q.empty()){
    auto tmp = q.top(); q.pop();
    ll nowp = tmp.second.first;
    ll nows = tmp.second.second;
    ll nowt = tmp.first;
    for(auto a:G[nowp]){
      ll to = a.first;
      ll newt = nowt + a.second.second;
      ll news = nows - a.second.first;
      if(news >= 0){
        if(newt < dist[to][news]){
          dist[to][news] = newt;
          q.push({newt, {to, news}});
        }
      }
    }
    ll newt_ = nowt + D[nowp];
    ll news_ = nows + C[nowp];
    news_ = min(5000LL, news_);
    if(newt_ < dist[nowp][news_]){
      dist[nowp][news_] = newt_;
      q.push({newt_, {nowp, news_}});
    }
  }
  for(int i=1; i<N; i++){
    ll ans = inf;
    rep(j,5001){
      ans = min(ans, dist[i][j]);
    }
    cout << ans << endl;
  }


  return 0;
}


Measured memory_bytes: 11360
#include <iostream>

using namespace std;

int main(void){
    int A, B, K;
    cin >> A >> B >> K;
    int common[100];
    int i;
    int check = 0;

    for(i = 100; i >= 1; i--){
        if(A % i == 0 && B % i == 0){
            common[check] = i;
            check++;
        }
    }

    cout << common[K-1] << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    string s,t;
    cin >> s;
    cin >> t;
    int l1 = s.length();
    int l2 = t.length();
    if (l2-l1 == 1){
        for (int i = 0; i < l1; i++){
            if(s[i] != t[i]){
                cout << "No" << endl;
                return 0;
            }
        }
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VB = vector<bool>;
using VVB = vector<VB>;

int main(int argc, char const *argv[]) {
  int num, k;
  cin >> num >> k;
  VI a(num);
  for (int i = 0; i < num; i ++) {
    cin >> a[i];
  }

  VVB dp1(num + 1, VB(k, false));
  dp1[0][0] = true;
  for(int i = 0; i < num; i ++) {
    for(int j = 0; j < k; j ++) {
      dp1[i + 1][j] = dp1[i][j];
    }
    for(int j = 0; j + a[i] < k; j ++) {
      dp1[i + 1][j + a[i]] = dp1[i + 1][j + a[i]] || dp1[i][j];
    }
  }
  VVI max1(num + 1, VI(k, 0));
  for(int i = 0; i <= num; i ++) {
    for(int j = 1; j < k; j ++) {
      max1[i][j] = max1[i][j - 1];
      if(dp1[i][j]) max1[i][j] = j;
    }
  }
  VVB dp2(num + 1, VB(k, false));
  dp2[num][0] = true;
  for(int i = num; i > 0; i --) {
    for(int j = 0; j < k; j ++) {
      dp2[i - 1][j] = dp2[i][j];
    }
    for(int j = 0; j + a[i - 1] < k; j ++) {
      dp2[i - 1][j + a[i - 1]] = dp2[i - 1][j + a[i - 1]] || dp2[i][j];
    }
  }
  VVI max2(num + 1, VI(k, 0));
  for(int i = 0; i <= num; i ++) {
    for(int j = 1; j < k; j ++) {
      max2[i][j] = max2[i][j - 1];
      if(dp2[i][j]) max2[i][j] = j;
    }
  }
  ll ans = 0;
  for(int i = 0; i < num; i ++) {
    bool b = a[i] >= k;
    for(int j = 0; j < k; j ++) {
      b |= max1[i][j] + max2[i + 1][k - j - 1] >= k - a[i];
    }
    if(!b) ans ++;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 202624
#include <bits/stdc++.h>
#define ll long long
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
// rep(i, 1, 4) --> {1,2,3,4}
// rep(i, 4, 1) --> {4,3,2,1}
// rep(it, end(v), begin(v)) --> *it

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> v(n);
    rep(i, 0, n)
        cin >> v[i];
    sort(begin(v), end(v));
    int ans = INT_MAX;
    rep(i, v[0], v[v.size()-1]+1)
    {
        int sum = 0;
        rep(j, 0, n)
        {
            sum += pow(v[j] - i, 2);
        }
        ans = min(ans, sum);
    }
    cout << ans;
    return 0;    
}

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

int main() {
    int A, B;
    int X;

    cin >> A >> B;
    if (A == B) {
        X = A + B;
    } else {
        X = max(A, B) * 2 - 1;
    }
    cout << X << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
typedef vector<int> VI;
typedef vector<VI> VVI;
const ll MOD = 1000000007;
#define REP(i, n) for(int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()

int main() {
	int n;
	cin >> n;
	cout << n * n * n;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
int n,t;
cin>>n>>t;
int a,b,sum;sum=1003;
while(n--)
{
    cin>>a>>b;
    if(b<=t)sum=min(a,sum);
}
if(sum==1003)cout<<"TLE";
else cout<<sum;
}




Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <cmath>
#include <numeric>
using namespace std;
#define rep(i,a,b) for(int64_t i=(a);i<(b);++i) // a ≦ i < b 
#define Rrep(i,a,b) for(int64_t i=(a);i>=(b);--i) // reverse repeat. a から b まで減少．
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend() //逆イテレータ
#define RANGE(a,b,c) (a).begin()+(b),(a).begin()+(c) // [b,c) イテレータ
#define INF 1000000000000000
#define MOD 1000000007
using PII = pair<int64_t, int64_t>;
using VI = vector<int64_t>;
using VVI = vector<VI>;
using VS = vector<string>;
using VP = vector<PII>;
using i64 = int64_t;
template<typename T> void invec(vector<T> &A){for(T& a:A) cin >> a;}
void submain();

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

int N, K; cin >> N >> K;
VI p(N); invec(p);

sort(ALL(p));


cout << accumulate(RANGE(p, 0, K), 0) << "\n";

return 0;
}

// 制限が緩い場合での愚直解を書く。
void submain(){

}

// コンテスト前はtemplate振り返り。
// 書いて考える．場合分け．情報整理．
// 問題文から考える。自分ができることから考える。
// 単純に分かる量から．愚直解を実装して研究．
// 境界，出力文字列 チェック．行末にスペース入れない．
// 可読性優先．高速化次点．
// まずは全探索，分割，次にDP(小さい問題から大きな問題)
// 制限を見る．境界に注意．求めたい量の変域．動かせる量．
// 偶奇，逆から，ソート，出現回数，出現位置，DP， 余事象，包除
// データ構造． 問題の特徴量．単調性→二分探索。逆から考える。
// 存在判定：構成方法，入力の特徴
// 構築問題。極端解を試す。
// 例外を十分に含む一般化．想像力の限界
// 小さい系から例示
// 代数的処理．前処理によるクエリ高速化．
// 始めは過剰に例示・場合分けしてもいい．各場合を確実に対処．
// 自明な例から処理，除外．
// 小数のときは，精度の設定する．doubel 変数に数値を入力するときは 123. とする．
// コーナーケース。境界値。数表出力プログラム作る
// 実行エラー：vector添え字超え．0割り．



Measured memory_bytes: 3620
def knapsack(items, budget)
	table = (0..1).map{ Array.new(budget+1, 0) }
	for i in 0..items.size-1
		c, v = items[i]
		for j in 0..budget
			x = table[0][j]
			y = (j >= c ? table[0][j-c] + v : 0)
			table[1][j] = x > y ? x : y
		end
		table << table.shift
	end
	table[0].max
end

n, k = gets.split.map(&:to_i)

hash = {}

n.times { 
	price, kind = gets.split.map(&:to_i)
	hash[kind] ||= []
	hash[kind] << price
}

hash.each{|kind, prices|
	i = 0
	hash[kind] = prices	
		.sort
		.reverse
		.inject([0]){|a, p|
			i += 1
			a + [a[-1] + p + 2 * i - 2]
		}
}

a = hash.values

table = (0..1).map{ Array.new(k+1, 0) }
for i in 0..a.size-1
	for j in 0..k
		table[1][j] = 
			(0..[a[i].size-1, j].min)
			.map{|l| table[0][j-l] + a[i][l]}
			.max
	end
	table << table.shift
end
p table[0][k]

Measured memory_bytes: 13732
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int minR = 0;
        int maxDiff = -1000000000;
        for (int i = 0; i < n; i++) {
            int r = scanner.nextInt();
            if (i == 0) {
                minR = r;
                continue;
            }
            int diff = r - minR;
            if (maxDiff < diff) {
                maxDiff = diff;
            }
            if (r < minR) {
                minR = r;
            }
        }
        System.out.println(maxDiff);
    }
}

Measured memory_bytes: 99648
#include<bits/stdc++.h>
using namespace std;
#define int long long int
int32_t main()
{
    int s, n;
    cin >> s >> n;
    vector<int> v(n);
    for(int i=0; i<n; i++)
    {
        cin >> v[i];
    }

    vector<int> v2;
    for(int i=0; i<n; i++)
    {
        if(i == 0)
        {
            int ans = v[0] + (s - v[n-1]);
            v2.push_back(ans);
        }
        else
        {
            int ans = v[i] - v[i-1];
            v2.push_back(ans);
        }
    }

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

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

    cout << ans << endl;
    return 0;
}


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

vector<vector<char> > getMinesNunAroundEachCell(vector<vector<char> > field) {
        
    auto output = field;

    for (int i = 0; i < field.size(); i++)
    {
        for (int j = 0; j < field.at(0).size(); j++)
        {
            if(output.at(i).at(j) == '#')
                continue;
                
            int counter = 0;
            
            for (int l = -1; l <= 1; l++)
            {
                for (int m = -1; m <= 1; m++)
                {
                    if(0 <= i+l && i+l < field.size() && 0 <= j+m && j+m < field.at(0).size()) {
                        if(field.at(i+l).at(j+m) == '#')
                            counter++;
                    }
                }
            }
            // cout << counter;
            output.at(i).at(j) = counter + '0';
            // cout << output.at(i).at(j);
        }
        // cout << endl;
    }
    
    return output;
}


int main() {
    int height, width;
    cin >> height >> width;
    vector<vector<char> > field(height, vector<char>(width));

    for (int i = 0; i < field.size(); i++)
    {
        for (int j = 0; j < field.at(0).size(); j++)
        {
            cin >> field.at(i).at(j);
            // cout << field.at(i).at(j);
        }
        // cout << endl;
    }

    auto output = getMinesNunAroundEachCell(field);
    for (int i = 0; i < output.size(); i++)
    {
        for (int j = 0; j < output.at(0).size(); j++)
        {
            cout << output.at(i).at(j);
        }
        cout << endl;
    }
    
    return 0;
}

Measured memory_bytes: 256
def main():
    N = int(input())
    a = [list(map(int, input().split())) for i in range(N)]
    
    now = [0] * N
    day = 0
    gamed_day = [-1] * N
    
    ind = [i for i in range(N)]

    while len(ind) > 0:
        next_ = []
        while len(ind) > 0:
            i = ind.pop(-1)
            if now[i] < N-1 and gamed_day[i] != day:
                all_finish = False
                want = a[i][now[i]] - 1
                if gamed_day[want] != day:# 今日試合していない
                    if a[want][now[want]] - 1 == i:# 相手の試合相手が自分
                        now[want] += 1
                        now[i] += 1
                        if now[want] < N-1:
                            next_.append(want)
                        if now[i] < N-1:
                            next_.append(i)
                        gamed_day[i] = day
                        gamed_day[want] = day
                        had_game = True
                        # print(day+1, i+1, want+1)
        ind = next_
        day += 1
    ok = True
    for i in range(N):
        if now[i] < N-1:
            ok = False
            break
    if ok:
        print(day)
    else:
        print(-1)


if __name__ == "__main__":
    main()


Measured memory_bytes: 36992