akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#define N_MAX 1000 /* 適当 */

typedef struct team { int num, score; } team;
int comp(void* a, void* b){ return (*(team*)b).score-(*(team*)a).score; }

int main(void){
     team team[N_MAX];
     int i, j, n=0;
	
     /* input */
     while(scanf("%d,%d",&i,&j), i!=0) team[n].num=i, team[n].score=j, n++;

     /* sort */
     qsort(team, n, sizeof(struct team), comp);

     /* search */
     while(~scanf("%d",&i)){
	  int prev=-1, rank=0; j=0;

	  while(1){
	       if(team[j].score!=prev) rank++, prev=team[j].score;
	       if(team[j].num==i) break;
	       j++;
	  }
	  printf("%d\n",rank);
     }
	
     return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define ANS cout << ans << endl
#define all(a) a.begin(),a.end()
#define SORT(a) sort(all(a))
#define REVERSE(a) reverse(all(a))
#define int long long
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define VIin(a) for(int i=0; i<a.size(); i++) cin >> a[i]
#define OUT(a) cout << a << endl
typedef vector<int> VI;
typedef vector<VI> VVI;
const int MOD=1e9+7;
const long long INF = 1LL << 60;
/*最大公約数*/int gcd(int x, int y) { return y ? gcd(y,x%y) : x;}
/*最小公倍数*/int lcm(int a, int b) { int g = gcd(a, b); return a / g * b; }
/*素数判定*/int isPrime(int n){if(n<2){return 0;}for(int i=2; i*i<=n; i++){if(n%i==0){return 0;}}return 1;}
/*約数列挙*/vector<int> getDivisor(int n){vector<int> v; for(int i=1; i*i<=n; i++){if(n%i==0){v.push_back(i);if(i!=n/i){v.push_back(n/i);}}}sort(v.begin(),v.end()); return v;}
//----------------------------------------------
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n; cin >> n;
    int ans = 0;
    FOR(i,1,n+1){
        if(i%2 == 1){
            VI y = getDivisor(i);
            if(y.size() == 8) ans++;
        }
    }
    ANS;

    return 0;
}



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

using namespace std;


void solve() {
    int N; cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];

    multiset<int> s;

    for (int i = 0; i < N; i++) {
        auto it = s.lower_bound(A[i]);
        if (it != s.begin()) s.erase(--it);
        s.insert(A[i]);
    }

    cout << s.size() << endl;
}


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

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

typedef long long s64;
typedef pair<int, int> pii;
int h[100001];
int A, B;
int n;

s64 all;
s64 ans;

bool check(s64 x)
{
    s64 tot = 0;
    for (int i = 1; i <= n; i++)
    {
        s64 p = 1ll * (h[i] + B - 1) / B;
        if (p <= x)
        {
            continue;
        }
        p = x;
        s64 q = h[i] - p * B;
        if (q < 0)
        {
            continue;
        }
        s64 r = q / (A - B);
        if (q % (A - B))
        {
            r++;
        }
        tot += r;
    }
    return tot <= x;
}

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

    s64 le = 0, ri = 1e18, mid;
    while (le + 3 < ri)
    {
        mid = (le + ri) / 2;
        if (check(mid))
        {
            ri = mid;
        }
        else
        {
            le = mid;
        }
    }
    for (s64 i = le; i <= ri; i++)
    {
        if (check(i))
        {
            cout << i << endl;
            return 0;
        }
    }
    return 0;
}


Measured memory_bytes: 640
import sys
from heapq import*
r=sys.stdin.readline
def g(E,n,s,g):
 F=[1e7]*-~n;F[s]=0
 H=[(0,s)]
 while H:
  c,u=heappop(H)
  if u==g:return c
  for f,v in E[u]:
   t=c+f
   if t<F[v]:F[v]=t;heappush(H,(t,v))
 return-1
def s():
 for e in iter(input,'0 0'):
  n,k=map(int,e.split())
  E=[[]for _ in[0]*-~n]
  for _ in[0]*k:
   f=[*map(int,r().split())]
   if f[0]:
    c,d,e=f[1:]
    E[c]+=[(e,d)];E[d]+=[(e,c)]
   else:print(g(E,n,*f[1:]))
if'__main__'==__name__:s()


Measured memory_bytes: 6308
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

#define INF 1200000000
#define ARRAY 110

int main() {
  int N, Max, Min;
  int A[ARRAY];

  scanf("%d", &N);
  for(int i=0; i<N; ++i)
    scanf("%d", &A[i]);

  Max = -INF;
  Min = INF;

  for(int i=0; i<N; ++i) {
    if(Max < A[i]) Max = A[i];
    if(Min > A[i]) Min = A[i];
  }

  printf("%d\n", Max-Min);

  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e9;
const ll mod = 1e9+7;
typedef pair<int,int> P;
typedef pair<pair<int,int>,pair<int,int>> PP;
#define rep(i,N) for(int i=0;i<N;i++)

int main(){
    int h,w;
    cin>>h>>w;
    int a[h][w];
    rep(i,h)rep(j,w)cin>>a[i][j];
    int cnt = 0;
    vector<PP> anst;
     rep(i,h){
        if(i%2==0){
            rep(j,w){
                if(j==w-1&&i==h-1)break;
                if(a[i][j]%2==1){
                    a[i][j]--;
                    if(j==w-1){
                        cnt++;
                        anst.push_back(make_pair(make_pair(i,j),make_pair(i+1,j)));
                        a[i+1][j]++;
                    }else{
                        cnt++;
                        anst.push_back(make_pair(make_pair(i,j),make_pair(i,j+1)));
                        a[i][j+1]++;
                    }
                }
            }
        }else{
            for(int j=w-1;j>=0;j--){
            if(j==0&&i==h-1)break;
                if(a[i][j]%2==1){
                    a[i][j]--;
                    if(j==0){
                        cnt++;
                        anst.push_back(make_pair(make_pair(i,j),make_pair(i+1,j)));
                        a[i+1][j]++;
                    }else{
                        cnt++;
                        anst.push_back(make_pair(make_pair(i,j),make_pair(i,j-1)));
                        a[i][j-1]++;
                    }
                }
            }
        }
    }
    cout<<cnt<<endl;
    for(auto itr : anst){
        cout<<itr.first.first+1<<" "<<itr.first.second+1<<" "<<itr.second.first+1<<" "<<itr.second.second+1<<endl;
    }
}

Measured memory_bytes: 5232
import scala.math.{min,max}

object Main {
  val sc = new java.util.Scanner(System.in)
  def solve(c: Int): Int = c match {
    case 0 => 0
    case 1 => 1
    case 5 => 1
    case 10 => 1
    case 50 => 1
    case 100 => 1
    case 500 => 1
    case n if n > 500 => 1 + solve(c-500)
    case n if n > 100 => 1 + solve(c-100)
    case n if n > 50 => 1 + solve(c-50)
    case n if n > 10 => 1 + solve(c-10)
    case n if n > 5 => 1 + solve(c-5)
    case n if n > 1 => 1 + solve(c-1)
  }

  def main(args: Array[String]) {
    while(true) {
      val n = sc.nextInt
      if(n == 0) return
      val c = 1000-n
      println(solve(c))
    }
  }
}

Measured memory_bytes: 44588
#!/usr/bin/env python3

import sys

(N,T) = map(int, input().split())
ts = list(map(int, input().split()))

sum = 0
end = 0
for i in range(N):
    if end <= ts[i]:
        sum += T
    else:
        sum += T - (end - ts[i])
    end = ts[i] + T
print(sum)


Measured memory_bytes: 26836
lit=[]
while True:
    try:
        lit.append(input())
    except EOFError:
        break
result=[0,0,0]
for i in lit:
    if int(i) >result[0]:
        result[2]=result[1]
        result[1]=result[0]
        result[0]=int(i)
        
    elif int(i)>result[1]:
        result[2]=result[1]
        result[1]=int(i)
    elif int(i)>result[2]:
        result[2]=int(i)
for i in result:
    print(i)


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

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

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

  int a, b;
  cin >> a >> b;

  if ((a + b) % 2 == 0) {
    cout << (a + b) / 2 << endl;
  } else {
    cout << "IMPOSSIBLE" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main()
{
    int m,d;cin >> m >> d;
    int cnt = 0;
    int pro  = 1,rem;
    int number;
    for(int i = 3;i <= m;i++)
    {
        for(int j = 22;j <= d;j++)
        {
            if(j%10 != 1)
            pro = j%10*(j/10);
            if(pro == i)cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}


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

def main():
    N = int(input())
    F = []
    for _ in range(N):
        # ex. "1 1" => "11" => 3.
        F.append(int(input().replace(" ", "", -1), 2))
    P = []
    for i in range(N):
        P.append(list(map(int, input().split())))

    ans = -10**7*N
    for i in range(1, 1<<10):
        tmp = 0
        for j,f in enumerate(F):
            # 両方のビットが立っている数 (=両方の店が営業している時間帯の個数) 
            c = bin(i&f).count("1")
            tmp += P[j][c]
        ans = max(ans, tmp)
    print(ans)

if __name__ == '__main__':
    main()


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

int n;

int main(void){
  cin >> n;
  int i = 0;
  while(true){
    if(pow(2, i) > n){
      break;
    }
    i++;
  }
  cout << pow(2, i - 1) << endl;
}


Measured memory_bytes: 512
import java.util.Scanner;


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

		int N = sc.nextInt();
		boolean result = true;

		int ti = 0;
		int xi = 0;
		int yi = 0;

		for (int i = 0; i < N; i++) {
			int t = sc.nextInt();
			int x = sc.nextInt();
			int y = sc.nextInt();

			int ta = Math.abs(t - ti);
			int xa = Math.abs(x - xi);
			int ya = Math.abs(y - yi);

			if (ta < xa + ya
				|| ta % 2 != (xa + ya) % 2) {
				result = false;
				break;
			}

			ti = t;
			xi = x;
			yi = y;
		}

		System.out.println(result ? "Yes" : "No");
	}
}

Measured memory_bytes: 88604
n = int(input())
S = input()
#右にある白，左にある黒
cnt = [0]*(n+1)
white = S.count(".")
black = 0
cnt[0] = white
for i in range(n):
    if S[i] == ".":
        white -= 1
    else:
        black += 1
    cnt[i+1] = black + white
print(min(cnt))

Measured memory_bytes: 68192
#include <iostream>

using namespace std;

int main(void) {
    int A, B;
    // get input ----------------------
    cin >> A >> B;
    // sontaku ------------------------
    if(A == 1) A = 14;
    if(B == 1) B = 14;
    // disp answer --------------------
    if(A == B) {
        cout << "Draw" << endl;
    } else if(A > B) {
        cout << "Alice" << endl;
    } else {
        cout << "Bob" << endl;
    }
    return 0;
}





Measured memory_bytes: 256
package main

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

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

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

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

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

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

var writer = bufio.NewWriter(os.Stdout)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

func solve() {
	x := 0
	ans := 0
	_, S := nextInt(), next()
	for _, c := range S {
		if c == 'I' {
			x++
			ans = max(ans, x)
		} else {
			x--
		}
	}
	out(ans)
}


Measured memory_bytes: 640
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        if(n==1)System.out.println("Hello World");
        if(n==2) {
        	System.out.println(sc.nextInt()+sc.nextInt());
        }
    }
}

Measured memory_bytes: 23124
#include<bits/stdc++.h>
#define MSET(x,y) memset(x,y,sizeof(x))
#define F first
#define S second
#define MP make_pair
#define PB push_back
#define SZ size()
#define M 100005
#define ll long long
#define ld long double
#define INF 1e18
#define endl "\n"
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define vll vector<ll>
#define sorrt(a) sort(a.begin(), a.end())
using namespace std;
ll MOD = 1000000007;
string yes = "YES\n";
string no = "NO\n";
#define PI 3.1415926535 


int32_t main() {
  fastio;
  ll n;
  cin>>n;
  vll a(n), b(n);
  for(ll i=0;i<n;i++) {
    cin>>a[i]>>b[i];
  }
  sorrt(a);
  sorrt(b);
  if(n%2) {
    cout<< b[(n-1)/2] - a[(n-1)/2] + 1 <<endl;
  } else {
    cout<< (b[n/2] + b[n/2 - 1]) - (a[n/2] + a[n/2 - 1]) + 1<<endl;
  }
}

Measured memory_bytes: 6364
#include <iostream>

using namespace std;

int main() {
	int w, h, x, y, r;
	cin >> w >> h >> x >> y >> r;

	if (x + r <= w && x - r >= 0 && y + r <= h && y - r >= 0)
		cout << "Yes\n";
	else cout << "No\n";

	return 0;
}


Measured memory_bytes: 3100
/* بِسْمِ اللَّهِ الرَّحْمَٰنِ الرَّحِيمِ */
//codeforces
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define FASTIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define mp make_pair
#define pb push_back
#define sz(v) ((int)v.size())
#define all(v) v.begin(), v.end()
void parseArray(ll* A,ll n){ for ( ll K = 0; K < n; K++){ cin >> A[K]; } }
ll modInverse(ll a, ll b){ return 1<a ? b - modInverse(b%a, a)*b/a : 1; }
ll gcd(ll a, ll b){ return b?gcd(b, a % b):a; }
ll lcm(ll a, ll b){ return (a*b)/gcd(a, b); }
ld dist(ld x, ld y, ld a, ld b){ return sqrt((x-a)*(x-a) + (y-b)*(y-b)); }
void debug(ll* a, ll n) { for ( ll k = 0; k < n; k++ ){ cerr << a[k] << " ";} cout << "\n"; }
#define PI 3.14159265358979323846

int main(){
	FASTIO;
	ll n; cin >> n;
	ll a[n]; parseArray(a, n);
	ll occ[n]; memset(occ, 0, sizeof occ);
	for ( int k = 0; k < n; k++ ) occ[a[k] - 1]++;
	for ( int k = 0; k < n; k++ ) a[k]--;
	ll ans = 0;
	for ( int k = 0; k < n; k++ )
		ans += (occ[k] * (occ[k] - 1)) / 2;
	for ( int k = 0; k < n; k++ ){
		if (occ[a[k]]) {
			ans -= (occ[a[k]] * (occ[a[k]] - 1)) / 2;
			ans += ((occ[a[k]] - 1) * (occ[a[k]] - 2)) / 2;
			cout << ans << "\n";
			ans -= ((occ[a[k]] - 1) * (occ[a[k]] - 2)) / 2;
			ans += (occ[a[k]] * (occ[a[k]] - 1)) / 2;
		}else {
			cout << ans << "\n";
		}
	}
	return 0;
}

Measured memory_bytes: 5760
import java.awt.Point;
import java.util.ArrayDeque;
import java.util.Scanner;
import java.util.*;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.Set;
import java.util.HashSet;
import java.util.Collection;


 
public class Main{
	
        static final Scanner sc=new Scanner(System.in);
        static int N=sc.nextInt();
        static int K=sc.nextInt();
        static int[]A=new int[N];
        
        
        
        
        
        public static void main(String[]args){
                int ichi=0;
                for(int i=0;i<N;i++){
                        A[i]=sc.nextInt();
                        if(A[i]==1){
                                ichi=i;
                        }
                }
                int sum=0;
                int KK=K-1;
                if((N-1)%(K-1)==0){
                System.out.println((N-1)/(K-1));}
                else{
                        System.out.println((N-1)/(K-1)+1);
                }
                
                

        }
        
        
        

		
	
}


Measured memory_bytes: 48412
ma = lambda :map(int,input().split())
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq

s = input()
co = collections.Counter(list(s))
f =True
if len(co) ==2:
    for it,cnt in co.items():
        if cnt!=2:
            f=False
else:f=False
yn(f)


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

using namespace std;

vector<int> a;
int n;

int main()
{
    //freopen("taskC.inp", "r", stdin);

    cin >> n;
    a.resize(n);

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

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

    cout << a[n/2] - a[n/2 - 1];

    return 0;
}


Measured memory_bytes: 640
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.Map;
import java.util.NavigableMap;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task solver = new Task();
        solver.solve(in, out);
        out.close();
    }

    static class Task {
        int N;
        long ans = 0;
        Map<String, Long> anagramCnt = new HashMap<>();

        void solve(InputReader in, PrintWriter out) {
            N = in.nextInt();
            for (int i = 0; i < N; ++i) {
                String s = in.next();
                NavigableMap<Character, Integer> charCnt = new TreeMap<>();
                for (char c : s.toCharArray()) {
                    int v = charCnt.containsKey(c) ? charCnt.get(c) : 0;
                    charCnt.put(c, v + 1);
                }
                StringBuilder sb = new StringBuilder();
                for (Map.Entry<Character, Integer> e : charCnt.entrySet()) {
                    sb.append(e.getKey()).append(e.getValue());
                }
                String key = sb.toString();
                long v = anagramCnt.containsKey(key) ? anagramCnt.get(key) : 0;
                anagramCnt.put(key, v + 1);
            }
            for (long v : anagramCnt.values()) {
                ans += v*(v - 1) / 2;
            }
            out.println(ans);
        }

    }

    static class InputReader {
        BufferedReader reader;
        StringTokenizer tokenizer;

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

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

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

        int[] nextIntArray(int size) {
            int[] arr = new int[size];
            for (int i = 0; i < size; i++) {
                arr[i] = nextInt();
            }
            return arr;
        }

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

        long[] nextLongArray(int size) {
            long[] arr = new long[size];
            for (int i = 0; i < size; i++) {
                arr[i] = nextLong();
            }
            return arr;
        }
    }
}

Measured memory_bytes: 100296
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<iomanip>
#include<queue>

using namespace std;

typedef long long ll;

typedef std::pair<int, int> ipair;
bool lessPair(const ipair& l, const ipair& r){return l.second < r.second;}
bool morePair(const ipair& l, const ipair& r){return l.second > r.second;}

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

const ll MOD = 1e9 + 7;
// const long long INF = 1LL<<60;
void add(long long &a, long long b) { a += b; if (a >= MOD) a -= MOD; }
void sub(long long &a, long long b) { a -= b; if (a < 0) a += MOD; }
void mul(long long &a, long long b) { a *= b; a %= MOD; }
ll llmin(ll a, ll b) { if (a < b) return a; else return b; }
ll llmax(ll a, ll b) { if (a < b) return b; else return a; }
ll llabs(ll a) { if (a >= 0) return a; else return - a; }
ll llmodpow(ll a, ll n) {
   if (n == 0) return 1;
   ll tmp = llmodpow(a, n / 2);
   mul(tmp, tmp);
   if (n & 1) mul(tmp, a);
   return tmp;
}

int main() {
   int N;
   string T;
   cin >> N >> T;
   int A[N];
   int ans = 0;
   for (int a = 0; a < N; a++) {
      string S = T.substr(a, N - a);
      memset(A, 0, sizeof(A));
      A[0] = S.size();
      int i = 1, j = 0;
      while (i < S.size()) {
         while (i + j < S.size() && S[j] == S[i + j]) ++j;
         A[i] = j;
         if (j == 0) { ++i; continue;}
         int k = 1;
         while (i + k < S.size() && k + A[k] < j) A[i + k] = A[k], ++k;
         i += k; 
         j -= k;
      }
      for (int b = 0; b < N; b++) {
         if (A[b] <= b) chmax(ans, A[b]);
      }
   }
   cout << ans << endl;
   return 0;
}


Measured memory_bytes: 256
#include<cstdio>
int n, s[3][110], x, ans;
int _max(int a, int b){
	if(a>b) return a;
	else return b;
}
int main() {
	scanf("%d", &n);
	for(int i=1; i<=2; i++)
		for(int j=1; j<=n; j++){
			scanf("%d", &x);
			s[i][j]=s[i][j-1]+x;
		}
	for(int i=1; i<=n; i++)
		ans=_max(ans, s[1][i]+s[2][n]-s[2][i-1]);
		printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n,k,sum=0; cin>>n>>k;
  vector<int> l(n);
  for(int i=0; i<n; i++) cin>>l[i];
  sort(l.rbegin(),l.rend());
  for(int i=0; i<k; i++) sum+=l[i];
  cout<<sum;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<iostream>
#include<string>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iomanip>
#include<cstdlib>
#include<ctime>
#include<set>
#include<map>
#include<utility>
#include<queue>
#include<vector>
#include<stack>
#include<sstream>
#include<algorithm>
/************************************************/
#define rep(i,n) for(int i=0;i<n;i++)
#define m_p make_pair
#define pb push_back
#define fr first
#define se second
#define forn(i,a,n) for(int i=a;i<n;i++)
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();i++)
#define pii pair<int,int>
#define vi vector<int>
#define ll long long
#define sz(s) s.size()
#define all(s) s.begin(),s.end()
#define zero(x) memset(x,0,sizeof(x))
#define vii vector<pair<int,int> >
#define mpis map<int,string>
#define mpii map<int,int>
#define mpsi map<string,int>
#define re return
#define mod 1000000007
/************************************************/
using namespace std;

long long get(){
	char c=getchar();
	long long x=0LL;
	while(c<'0'||c>'9')
	c=getchar();
	while(c>='0'&&c<='9'){
		x*=10LL;
		x+=(c-'0');
		c=getchar();
	}
	return x;
}
string i_t_s(int x){
	string t="";
	while(x){
		t+=x%10+'0';
		x/=10;
	}
	reverse(all(t));
	re t;
}
int s_t_i(string t){
	int x=0;
	rep(i,sz(t)){
		x=x*10+(t[i]-'0');
	}
	re x;
}
int n,q;
int a[200001];
int dfs(int x){
	if(a[x]==x)
	re x;
	a[x]=dfs(a[x]);
	re a[x];
}
int main(){
	ios::sync_with_stdio(0);
	cin>>n>>q;
	rep(i,n)
	a[i]=i;
	while(q--){
		int t,x,y;
		cin>>t>>x>>y;
		if(t){
			dfs(x);
			dfs(y);
			if(a[x]!=a[y])
			cout<<"0\n";
			else
			cout<<"1\n";
		}else{
			a[dfs(y)]=dfs(x);
		}
	}
	re 0;
}


Measured memory_bytes: 4352
N, M = map(int, input().split())
link = [[] * N for i in range(N)]
for i in range(M):
    a, b = map(lambda x: int(x) - 1, input().split())
    link[a].append(b)
    link[b].append(a)

flag = False

for i in range(len(link[0])):
    for j in link[link[0][i]]:
        if j == N-1:
            flag = True

if flag:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Measured memory_bytes: 38320
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <bitset>
#include <cassert>
#include <random>
#include <queue>
#include <set>
#define int long long

using namespace std;

mt19937 rnd(228228);

typedef pair<int, int> pa;
typedef long double ld;
typedef long long ll;

const int N = 102, inf = 1e9;
int dp[N][N][2];

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int h, w;
    cin >> h >> w;
    vector<vector<char>> a(h, vector<char>(w));

    for (vector<char>& i : a) {
        for (char& j : i)
            cin >> j;
    }
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            dp[i][j][1] = inf, dp[i][j][0] = inf;
    if (a[0][0] == '.')
        dp[0][0][0] = 0;
    else
        dp[0][0][1] = 1;

    for (int r = 0; r < h; ++r) {
        for (int c = 0; c < w; ++c) {
            if (r > 0) {
                if (a[r][c] == '.')
                    dp[r][c][0] = min(min(dp[r - 1][c][0], dp[r - 1][c][1]), dp[r][c][0]);
                else
                    dp[r][c][1] = min(min(dp[r - 1][c][0] + 1, dp[r - 1][c][1]), dp[r][c][1]);
            }
            if (c > 0) {
                if (a[r][c] == '.')
                    dp[r][c][0] = min(min(dp[r][c - 1][0], dp[r][c - 1][1]), dp[r][c][0]);
                else
                    dp[r][c][1] = min(min(dp[r][c - 1][0] + 1, dp[r][c - 1][1]), dp[r][c][1]);
            }
        }
    }


    cout << min(dp[h - 1][w - 1][0], dp[h - 1][w - 1][1]);
}

Measured memory_bytes: 512
#include<iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
#define rep(i,ra,re) for((i)=ra;(i)<(re);(i)++)
#define _rep(i,ra,re) for((i)=ra;(i)>(re);(i)--)
#define rep_(i,ra,re) for((i)=ra;(i)<=(re);(i)++)
#define _rep_(i,ra,re) for((i)=ra;(i)>=(re);(i)--)
#define put(n) cout << n << " "; 
#define puts(n) cout << n << endl;
#define pu(n) cout << n;
#define kic 1000000007
int i,j,k,l;
static const int MAX_N=10e5;
int A[MAX_N];
int main(void){
	int N;
		cin >> N;
	rep(i,0,N)
		cin >> A[i];
	sort(A,A+N);
	int ans=A[N/2-1]-A[N/2];
	puts(ans*(-1));
	return 0;
}


Measured memory_bytes: 640
def solve():
    N, W = map(int, input().split())
    w = []
    v = []
    for i in range(N):
        tmpw, tmpv = map(int, input().split())
        w.append(tmpw)
        v.append(tmpv)

    dp = [[0 for i in range(W+1)] for j in range(N+1)]

    for i in range(N+1):
        dp[i][0] = 0
    
    for j in range(W+1):
        dp[0][j] = 0

    for i in range(1,N+1):
        for sum_w in range(1, W+1):
            if sum_w - w[i-1] >= 0:
                dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][sum_w - w[i-1]] + v[i-1])
            
            dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][sum_w])
        
    print(dp[N][W])

if __name__ == '__main__':
    solve()

Measured memory_bytes: 173576
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define scn(n) scanf("%d",&n)
#define lscn(n) scanf("%lld",&n)
#define pri(n) printf("%d",n)
#define lpri(n) printf("%lld",n)
#define priln(n) printf("%d\n",n)
#define lpriln(n) printf("%lld\n",n)
#define F first
#define S second
const int mod=1e9+7;

int main()
{
    int t=1;
   // cin>>t;

    while(t--)
    {
        int n,x,t;
        cin>>n>>x>>t;

        ll ans=(n+x-1)/x;
        ans=ans*t;
        cout<<ans;
    }
}

Measured memory_bytes: 3596
n,m=map(int,input().split())
flag=list(1 for _ in range(n+1))
count=list(0 for _ in range(n+1))
ans=0
for i in range(m):
    x=int(input())
    flag[x]=0

if n==1:
    ans=1
else:
    if flag[1]==1:
        count[1]=1
    if flag[2]==1:
        count[2]=count[1]+1
    for i in range(3,n+1):
        if flag[i]==1:
            count[i]=count[i-1]+count[i-2]
            
    ans=count[n]
print(ans%(10**9+7))
           

Measured memory_bytes: 470708
#include <cstdio>
#include <vector>
typedef long long ll;

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

using namespace std;

int A[999999], T[999999];

ll dc(int l, int r) { 
    if (l+1 >= r) return 0; 
    else if (l+2 == r) { 
        if (A[l] <= A[l+1]) return 0; 
        swap(A[l], A[l+1]);
        return 1; 
    } else {
        int m = (l+r)/2;
        ll cl = dc(l, m);
        ll cr = dc(m, r);
        ll c = 0;
        int i=l, j=m, k=l;
        while (i<m && j<r) { 
            if (A[i] <= A[j]) T[k++] = A[i++]; 
            else {
                T[k++] = A[j++];
                c += m-i; 
            }
        }
        while (i<m) T[k++] = A[i++]; 
        while (j<r) T[k++] = A[j++]; 
        copy(T+l, T+r, A+l);
        return cl + cr + c;
    }
}
int main(){
    int i,n;
    scanf("%d",&n);
    rep(i,n) scanf("%d",A+i); printf("%lld\n",dc(0,n));
}

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

int main(){
    int AB, BC, CA;
    int maxval;
    int ans;
    cin >> AB >> BC >> CA;
    maxval =  max({AB, BC, CA});
    if(maxval == AB){
       ans = (BC * CA) / 2; 
    }else if(maxval == BC){
       ans = (AB * CA) / 2;     
    }else{
       ans = (AB * BC) / 2;     
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define D(x) cout << #x << "=" << x <<endl; 
#define De(...)
#define hrp(i, l, r) for(register int i = l; i <= r; i++)
using namespace std; 

int _; 

int n,q,a[100050],b[100050],c[100050],cnt[100050];
long long sum=0;

int main()
{
	//for(scanf("%d",&_);_;_--)
	for(int i=0;i<100050;i++)
		cnt[i]=0;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d",a+i);
		sum += a[i];
		cnt[a[i]]++;
	} 
	scanf("%d",&q);
	for(int i=0;i<q;i++)
		scanf("%d%d",b+i,c+i);
	for(int i=0;i<q;i++)
	{
		sum += (c[i]-b[i])*cnt[b[i]];
		cnt[c[i]] += cnt[b[i]];
		cnt[b[i]]=0;
		printf("%lld\n",sum);
	}
	return 0;
}

Measured memory_bytes: 5368
#include<stdio.h>
int min(int a,int b){
  if(a<=b){
    return a;
  }
  else {
    return b;
  }
}


int main(){
  int N;
  scanf("%d",&N);
  int b[N-1];
  int a[N];
  
  for (int i=0;i<=N-1;i++){
    scanf("%d",&b[i]);
  }
  
  a[0]=b[0];
  
  for (int i=1;i<=N-2;i++){
    a[i]=min(b[i],b[i-1]);
  }
  
  a[N-1]=b[N-2];
  
  int ans=0;
  for (int i=0;i<N;i++){
    ans+=a[i];
  }
  
  printf("%d",ans);
  
  return 0;
}

  


Measured memory_bytes: 1684
#include <iostream>
#include <vector>

using namespace std;

int main() {
  int N;
  cin >> N;
  vector<int> a(N);
  for (int i = 0; i < N; i++) {
    cin >> a[i];
  }

  int i = 1;
  int n{};
  while(n<N) {
    i = a[i-1];
    ++n;
    if (i==2) break;
  }
  cout << (n==N?-1:n) << endl;
  return 0;
}


Measured memory_bytes: 640
#include<iostream>
using namespace std;
int main()
{
  int n,a,i;
  cin >> n;
  for(i=0;i<n;i++){
    cin >> a;
    if(a%2==0 && a%3!=0 && a%5!=0){
      cout << "DENIED" << endl;
      return 0;
    }
  }
  cout << "APPROVED" << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <string>
#include <sstream>
#include <algorithm>
#include <random>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <cassert>
#include <climits>
#include <bitset>
#include <functional>
#include <iomanip>
#include <random>

#define FOR_LT(i, beg, end) for (int i = (int)(beg); i < (int)(end); i++)
#define FOR_LE(i, beg, end) for (int i = (int)(beg); i <= (int)(end); i++)
#define FOR_DW(i, beg, end) for (int i = (int)(beg); (int)(end) <= i; i--)
#define REP(n)              for (int repeat_index = 0; repeat_index < (int)n; repeat_index++)


using namespace std;

constexpr size_t kMax = 100000;

int cs[kMax + 1] = { 0 };

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout << fixed << setprecision(20);

	int n; cin >> n;
	FOR_LT(i, 0, n) {
		int a; cin >> a;
		cs[a]++;
	}

	int64_t sum = 0;
	FOR_LE(i, 1, kMax) {
		sum += i * cs[i];
	}

	int q; cin >> q;
	FOR_LT(i, 0, q) {
		int b, c; cin >> b >> c;
		sum += cs[b] * (c - b);
		cs[c] += cs[b];
		cs[b] = 0;
		cout << sum << endl;
	}

	return 0;
}

Measured memory_bytes: 4040
/*~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=
*$* WRITER:kakitamasziru/OxOmisosiru *$*
~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=*/
#ifdef LOCAL_JUDGE
#define _GLIBCXX_DEBUG
#endif
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <iomanip>
#include <limits>//setprecision
//#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
//#include <unordered_set> //unordered_set
#include <stack> // stack
#include <deque> // deque
#include <math.h>//pow,,,
#include <cmath>//abs,,,
#include <bitset> // bitset
#define endl "\n";
//It is so troublesome that I include bits/stdc++.h !
using namespace std;

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
const long long INF = 100100100100100;
const long long MOD = 1000000007;
typedef pair<int,int> P;

//Solve N^M. This, mod_pow use Iterative Square Method.
long long mod_pow(long long N, long long M) {
    if (M == 0) return 1;
    long long res = mod_pow((N * N) % MOD, M / 2);
    //最下位ビット(*N)が1の時は単独でNをかける
    if (M & 1) res = (res * N) % MOD;

    return res %= MOD;
}

int gcd(long long a, long long b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}
long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b ;
}

int main() {
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N;cin >> N;
    vector<int> OUTPUT;
    int count = 0;
    for(int i = 2;i<=55555;i++){
        if(count == N){
            break;
        }
        int now = i;
        int prv = i;
        while(now > 0){
            for(int j = 2;j<=(int)sqrt(now);j++){
                if(now % j == 0){
                    now /= j;
                    break;
                }
            }
            if(prv == now && now == i){
                //5で割った余りが1になるような数を選ぶことで5個選んだ時に必ず5で割れる
                if(now % 5 == 1){
                    OUTPUT.push_back(i);
                    count++;
                }
                break;
            }
            else{
                break;
            }
        }
    }
    for(int V : OUTPUT) cout << V << endl;
}


Measured memory_bytes: 3676
#include <iostream>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
using namespace std;

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

int main(){
    int N;
    cin >> N;
    map<ll, int> mp_D;
    rep(i, N){
        ll a;
        cin >> a;
        mp_D[a]++;
    }
    int M;
    cin >> M;
    map<ll, int> mp_T;
    rep(i, M){
        ll a;
        cin >> a;
        mp_T[a]++;
    }
    bool is = true;
    for(auto mp : mp_T){
        if(mp_D.count(mp.first) == 0){
            is = false;
            break;
        }
        if(mp_D[mp.first] < mp.second){
            is = false;
            break;
        }
    }
    if(is) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}

Measured memory_bytes: 25216
#include <bits/stdc++.h>
 
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
 
#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=(int)(a)-1;i>=(int)(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)
 
#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
 
// #define DEBUG
 
#ifdef DEBUG
    #define dump(...) fprintf(stderr, __VA_ARGS__)
#else
    #define dump(...)
#endif
 
template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}
 
using namespace std;
using ll=long long;
using vi=vector<int>;
using vll=vector<ll>;
 
const double EPS = 1e-10;
const double PI = acos(-1.0);
const ll inf =1LL << 62;
const ll mod=1000000007LL;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
 
 
ll extgcd(ll a,ll b,ll& x,ll& y){x=1,y=0;ll g=a;if(b!=0) g=extgcd(b,a%b,y,x),y-=a/b*x;return g;}
ll ADD(const ll &a, const ll &b,const ll &mod) { return (a+b)%mod;}
ll SUB(const ll &a, const ll &b,const ll &mod) { return (a-b+mod)%mod;}
ll MUL(const ll &a, const ll &b,const ll &mod) { return (1LL*a*b)%mod;}
ll DIV(const ll &a, const ll &b,const ll &mod) {ll x,y; extgcd(b,mod,x,y);return MUL(a,(x+mod)%mod,mod);}
 
random_device rd;
mt19937 mt(rd());
uniform_int_distribution<int> dice(1,6);
uniform_real_distribution<double> score(0.0,10.0);
 
vector<string> res;

void dfs(string cs, char before){
    if(before == 'a'){
        res.push_back(cs);
        return;
    }

    char after = before - 1;
    int apos = cs.find(after),
        bpos = cs.find(before);

    if(apos == string::npos){
        if(bpos != string::npos) return;
        dfs(cs, after);
    }
    else {
        if(bpos == string::npos){
            dfs(cs, after);
            bpos = 12345;
        }

        do {
            if(bpos < apos) return;

            cs[apos] = before;
            dfs(cs, after);
            cs[apos] = after;
        } while((apos = cs.find(after, apos + 1)) != string::npos);
    }
}

int main(void){
    for(string in; cin >> in, in != "#";){
        res.clear();

        dfs(in, 'z');
        uniq(res);

        int sz = res.size();
        cout << sz << endl;
        if(sz <= 10){
            for(auto & e : res){
                cout << e << endl;
            }
        }
        else {
            rep(i, 5){
                cout << res[i] << endl;
            }
            rep(i, sz - 5, sz){
                cout << res[i] << endl;
            }
        }
    }

    return 0;
}

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

int main() {

  char c; cin >> c;
  if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
    cout << "vowel" << endl;
  }
  else {
    cout << "consonant" << endl;
  }
    
}


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

int main(){
  int a,b;
  string s;
  cin >> a >> b >> s;
  rep(i,a+b+1){
    if(i == a){
      if(s[i] != '-'){
        puts("No");
        return 0;
      }
    }
    else{
      if(s[i] == '-'){
        puts("No");
        return 0;
      }
    }
  }
  puts("Yes");
  return 0;
}


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

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

typedef long long ll;
const ll MOD = 1e9 + 7;
const int MAX_N = 2 * 1e5;
const int MAX_Q = 2 * 1e5;

int main() {
  int N, Q;
  static std::vector<int> children[MAX_N];

  ll cnt[MAX_N] = {};

  std::cin >> N >> Q;
  rep(i, N - 1) {
    int a, b;
    std::cin >> a >> b;
    children[a - 1].push_back(b - 1);
  }

  rep(j, Q) {
    int p, x;
    std::cin >> p >> x;
    cnt[p - 1] += x;
  }

  rep(i, N) {
    for(int c : children[i]) {
      cnt[c] += cnt[i];
    }
  }

  rep(i, N) std::cout << cnt[i] << " ";
}


Measured memory_bytes: 14848
{-# LANGUAGE BangPatterns #-}
import Control.Monad
import Data.Maybe
import Debug.Trace
import Data.List
import qualified Data.Map.Strict as Map
import qualified Data.IntMap.Strict as IntMap
import qualified Data.Set as Set
import qualified Data.IntSet as IntSet
import Data.Functor
-- import Data.Array
import Data.Array.Unboxed
import Control.Monad.ST
import Data.Array.ST

main :: IO ()
main = do
  n <- readLn :: IO Int
  as <- map read . words <$> getLine :: IO [Int]
  solve' n as

solve' :: Int -> [Int] -> IO ()
solve' n as = do
  let mp = foldl' go IntMap.empty . reverse $ zip as [1..n]
      m = sum . IntMap.elems $ mp
  print m
  if m == 0 
    then return ()
    else putStrLn . unwords . map show $ IntMap.keys mp
  where
    arr = listArray (1, n) as :: Array Int Int
    go :: IntMap.IntMap Int -> (Int, Int) -> IntMap.IntMap Int
    go mp (a, i) = newmp
      where
        bi = ((sumbs `mod` 2) + arr!i) `mod` 2
        newmp = if bi /= 0
          then IntMap.insert i bi mp
          else mp
        sumbs = sum $ catMaybes [ IntMap.lookup (i * j) mp | j <- [2..(n `div` i)]]


Measured memory_bytes: 65532
import java.util.*;
import java.io.*;

public class Main {
	static int[] c;
	static int[] f;
	static int k;
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		int n = Integer.parseInt(st.nextToken());  k = Integer.parseInt(st.nextToken());
		f = new int[n];
		Arrays.fill(f, -1);
		c = new int[n];
		st = new StringTokenizer(in.readLine());
		for(int i = 0; i < n; i++) {
			c[i] = Integer.parseInt(st.nextToken());
		}
		solve(0);
		System.out.println(f[0]);
	}
	public static int solve(int idx) {
		if(f[idx] != -1) {return f[idx];}
		if(idx == f.length - 1) {return 0;}
		int min = Integer.MAX_VALUE;
		for(int i = idx + 1; i < idx + k + 1 && i < f.length; i++) {
			int m = Math.abs(c[i] - c[idx]);
			m += solve(i);
			if(m < min) {
				//System.out.println(m + "," + i + "," + idx);
				min = m;
			}
		}

		f[idx] = min;
	//	System.out.println(f[idx] + "," + idx);
		return min;
	}
}


Measured memory_bytes: 45716
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<cstdio>
#define LL long long
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define INF 0x3f3f3f3f
#define Inf 1000000000000000000LL
#define F first
#define S second
using namespace std;
typedef pair<int,int>pii;
typedef pair<pii,int>piii;
const int maxn=2010;
int n,n3;
int a[3*maxn],b[maxn];
int dp[maxn][maxn];
int ans,ans2;
vector<piii>vis;
void update(int i,int j,int k){
	vis.pb(mp(mp(i,j),k));
	vis.pb(mp(mp(j,i),k));
}
void init(){
	memset(b,-0x3f,sizeof b);
	memset(dp,-0x3f,sizeof dp);
	dp[a[1]][a[2]]=b[a[1]]=b[a[2]]=ans2;
}
void solve(){
	for(int i=3;i<=n3;i+=3,vis.clear()){
		if(a[i]==a[i+1]&&a[i]==a[i+2]){
			ans2--;
			continue;
		}
		for(int _=0;_<3;_++){
			swap(a[i],a[i+1]),swap(a[i+1],a[i+2]);
			update(a[i],a[i+1],max(ans,dp[a[i+2]][a[i+2]]+1));
			for(int j=1;j<=n;j++){
				if(a[i+1]==a[i+2])update(j,a[i],dp[j][a[i+1]]+1);
				update(j,a[i],b[j]);
			}
		}
		for(auto j:vis){
			int e=j.F.F;
			int f=j.F.S;
			int g=j.S;
			dp[e][f]=max(dp[e][f],g);
			b[e]=max(b[e],g);
			ans=max(ans,g);
		}
	}
}
int main(){
	cin>>n;
	n3=3*n;
	for(int i=1;i<=n3;i++)cin>>a[i];
	init();
	solve();
	cout<<ans-ans2<<endl;
	return 0;
}

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

int main(){
	ll n;
	cin >> n;
	ll ans=10000000000050;
	for(ll i=1; i*i<=n; i++){
		if(n%i) continue;
		ans = min(ans, i+n/i-2);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

int main() {
    int a, b, c, k;
    cin >> a >> b >> c >> k;
    for (int i = 0; i <= k; ++i) {
        for (int j = 0; i+j <= k; ++j) {
            for (int l = 0; i+j+l <= k; ++l) {
                int aa = a, bb = b, cc = c;
                for (int m = 0; m < i; ++m) aa *= 2;
                for (int m = 0; m < j; ++m) bb *= 2;
                for (int m = 0; m < l; ++m) cc *= 2;
                if(aa < bb && bb < cc){
                    puts("Yes");
                    return 0;
                }
            }
        }
    }
    puts("No");
    return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
int main() {
  int r;
  cin >> r;
  if (r < 1200) {
    cout << "ABC" << endl;
  } else if (r < 2800) {
    cout << "ARC" << endl;
  } else {
    cout << "AGC" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
    #include<stdio.h>
    //#include <bits/stdc++.h>
    #include<vector>
    #include<algorithm>
    #include<string>
    #include<cstring>
    #include<math.h>
    #include<sstream>
    #include<set>
    #include<map>
    #include<queue>

    using namespace std;
    using Graph = vector<vector<int>>;

    #define INF 10000000
    #define rep(i,n)for(int i=0;(i)<(int)(n);i++)
    #define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
    #define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
    #define vec(type,n) vector<type>(n)
    #define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))

    const int dx[4] = {1,0,-1,0};
    const int dy[4] = {0,1,0,-1};
    
    
    
    int main(){
      int n;
      int year = 3650;
      while(cin>>n){
      if(n==0)break;
      long long dp[n];

      

      int j=0;
      dp[0] = 1;
      dp[1] = 1;
      dp[2] = 2;
      REP(i,3,n){
        dp[i] = dp[i-1]+dp[i-2]+dp[i-3];
      }
      int res;
      if(dp[n]%year)res = dp[n]/year+1;
      else res = dp[n]/year;
      cout << res <<endl;
      }
    }

      
      

     
    

    

     


Measured memory_bytes: 3004
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define MAXN 1000100
#define ll long long
#define inf 1000000000
double n,m, pi;
int main()
{
	pi = 3.1415926535;
	scanf("%lf",&n);
	n = n*2.0*pi;
	printf("%.6lf\n",n);
	
	return 0;
}

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

int main(){
	int n, i, s=0;
	cin >> n;
	int a[n+1];
	for (i=1;i<=n;i++) cin >> a[i];
	
	for (i=1;i<=n;i++){
		if (a[i]%2==0)
		   if (a[i]%3==0 || a[i]%5==0)
		      s++;
		   else{
		   	  cout << "DENIED";
		   	  return 0;
		   }
	}
	cout << "APPROVED";
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int k,a,b;
  cin>>k>>a>>b;
  int ans=k;
  for(int i=1;;i++){
    if(a<=ans*i && ans*i<=b){
      cout<<"OK"<<endl;
      return 0;
    }
    if(ans*i>b)break;
  }
  cout<<"NG"<<endl;
  return 0;
}

Measured memory_bytes: 3632
dic = {"a":0,"b":25,"c":24,"d":23,"e":22,"f":21,"g":20,"h":19,"i":18,"j":17,"k":16,"l":15,"m":14,"n":13,"o":12,"p":11,"q":10,"r":9,"s":8,"t":7,"u":6,"v":5,"w":4,"x":3,"y":2,"z":1}
ls = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]

s = input()
k = int(input())
s_l = []
for i in range(len(s)):
    s_l.append(s[i])

for i in range(len(s_l)):
    if dic[s_l[i]] <= k:
        k -= dic[s_l[i]]
        s_l[i] = "a"

if k > 0:
    s_l[-1] = ls[((26 - dic[s_l[-1]]) + k)%26]

for i in range(len(s_l)):
    print(s_l[i],end = "")
print()


Measured memory_bytes: 55584