akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;
class Program
{
	static void Main(string[] args)
	{
		int N = int.Parse(Console.ReadLine());
		string[] str = Console.ReadLine().Split();
		int[] A = new int[N+2];
		int sum = 0;
		for(var i=1;i<N+1;i++){
			A[i] = int.Parse(str[i-1]);
			sum += Math.Abs(A[i] - A[i-1]);
		}
		sum += Math.Abs(A[N]);
		for(var i=1;i<N+1;i++){
			int sumi = sum;
			if(A[i] > A[i-1] && A[i] > A[i+1])
				sumi -= 2 *(A[i] - Math.Max(A[i-1],A[i+1]));
			else if(A[i] < A[i-1] && A[i] < A[i+1])
				sumi -= -2 * (A[i] - Math.Min(A[i-1],A[i+1]));
			Console.WriteLine(sumi);
		}
	}
}

Measured memory_bytes: 25948
#include<iostream>
#include <cstring>
using namespace std;
int dp[100000];
int n,a[100000],k;

int topdown()
{
	dp[n-1]=0;

	for(int i=n-2;i>=0;i--)
	{
		dp[i]=1e9;
		for(int j=1;j<=k;j++)
		{
          	if(i+j<n)
				dp[i]=min(dp[i] , abs(a[i]-a[i+j])+dp[i+j]);
		}
	}
	return dp[0];
}

int main()
{
	memset(dp,-1,sizeof(dp));
	cin>>n>>k;
	for(int i=0;i<n;i++)
		cin>>a[i];

	cout<<topdown();

	return 0;
}


Measured memory_bytes: 4420
#include<stdio.h>
#include<string.h>

typedef long long LL;
char a[15];
int n;

LL f(int x)
{
    int i;
    LL dap=0,res=0;
    for(i=0;i<n;i++){
        dap*=10,dap+=a[i];
        if(x%2)res+=dap,dap=0;
        x/=2;
    }
    return res+dap;
}

int main()
{
    LL res=0;
    int i;
    scanf(" %s", a);
    n=strlen(a);
    for(i=0;i<n;i++)a[i]-='0';
    for(i=0;i<(1<<(n-1));i++){
        res+=f(i);
    }
    printf("%lld", res);
    return 0;
}


Measured memory_bytes: 128
//ABC164 B

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reps(i, s, n) for(int i = s; i < (int)(n); i++)
const lint mod = 1000000007;


lint ans = 0;
lint a,b,c,d;

int main() {
  cin >> a >> b >> c >> d;

/*   rep(i,n){
    scanf("%lld",&a[i]);
  } */
  
  while(true){
    c -= b;
    if(c <= 0){
      printf("Yes\n");
      break;
    }
    
    a -= d;
    if(a <= 0){
      printf("No\n");
      break;
    }
  }

  //printf("%lld\n",ans);
}


Measured memory_bytes: 3632
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;
using ll = long long int;

const ll INF = 1LL << 60;
const int L = 2010;
ll dp[L][L], num[L][L];

void update_dp(int nl, int nr, int pl, int pr, ll a) {
    if(dp[nl][nr] > dp[pl][pr] + a) {
        dp[nl][nr] = dp[pl][pr] + a;
        num[nl][nr] = num[pl][pr];
    }
    else if(dp[nl][nr] == dp[pl][pr] + a) {
        num[nl][nr] += num[pl][pr];
    }
    num[nl][nr] = min(num[nl][nr], INF);
}

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

    int N = s.size();
    fill(dp[0], dp[N+1], INF);
    for(int i=0; i<=N; i++) dp[i][i] = 0, num[i][i] = 1;
    for(int i=0; i<N; i++) dp[i][i+1] = 0, num[i][i+1] = 1;

    for(int d=2; d<=N; d++) {
        for(int l=0; l<=N-d; l++) {
            int r = l + d;
            if(s[l] == s[r-1]) {
                update_dp(l, r, l+1, r-1, 0);
            }
            else {
                update_dp(l, r, l+1, r, 1);
                update_dp(l, r, l, r-1, 1);
            }
        }
    }

    if(num[0][N] < K) {
        cout << "NONE" << endl;
        return 0;
    }
    
    int l = 0, r = N;
    string ans = "";

    while(r - l > 1) {
        if(s[l] == s[r-1]) {
            ans += s[l];
            l++; r--;
        }
        else if(dp[l+1][r] < dp[l][r-1]) {
            ans += s[l];
            l++;
        }
        else if(dp[l][r-1] < dp[l+1][r]) {
            ans += s[r-1];
            r--;
        }
        else if(s[l] < s[r-1]) {
            if(K <= num[l+1][r]) {
                ans += s[l];
                l++;
            }
            else {
                K -= num[l+1][r];
                ans += s[r-1];
                r--;
            }
        }
        else if(s[r-1] < s[l]) {
            if(K <= num[l][r-1]) {
                ans += s[r-1];
                r--;
            }
            else {
                K -= num[l][r-1];
                ans += s[l];
                l++;
            }
        }
    }
    
    string res = "";
    res += ans;
    if(r - l == 1) res += s[l];
    reverse(ans.begin(), ans.end()); res += ans;
    cout << res << endl;
}



Measured memory_bytes: 57292
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <algorithm>

#include <bits/stdc++.h>
#include <cmath>
#include <limits>

using namespace std;
typedef long long LL;
using Graph = vector<vector<int>>;

static long long INF = (1LL<<62);

int PARENT[200002] = {0};
int RANK[200002] = {0};
int GRPN[200002] = {0};

void init(int L){
	if(L<1) return;
	for(int i=0; i<L; i++){
		PARENT[i]=i;
		RANK[i]=0;
	}
}

int root(int x){
	if(x<0) return -1;
	if(PARENT[x]==x){
		return x;
	}
	else{
		PARENT[x] = root(PARENT[x]);
		return PARENT[x];
	}
}

int same(int x, int y){
	if(x==y) return 1;
	if(root(x)==root(y)){
		return 1;
	}
	else{
		return 0;
	}
}

void combine(int x, int y){
	if(x==y) return;

	int a = root(x);
	int b = root(y);
	if(a==b) return;

	if(RANK[x]<RANK[y]){
		PARENT[b] = a;
	}
	else{
		PARENT[a] = b;
		if(RANK[x]==RANK[y]) RANK[x] += RANK[y];
	}
}

int main(int argc, char* argv[]){
	cin.tie(0);
	ios::sync_with_stdio(false);

	int N, M;
	cin >> N >> M;
	init(N);
	for(int i=0; i<M; i++){
		int a, b;
		cin >> a >> b;
		combine(a-1, b-1);
	}
	for(int i=0; i<N; i++){
		int c = root(i);
		GRPN[c]++;
	}
	int ans = 0;
	for(int i=0; i<N; i++){
		int u = GRPN[i];
		if(u > 0 && ans < u){
			ans = u;
		}
	}
	printf("%d\n", ans);
	return 0;
}



Measured memory_bytes: 11352
N = int(input())
time_coor = []
for n in range(N+1):
    if n==0:
        time_coor.append([0, 0, 0])
    else:
        time_coor.append(list(map(int, input().split())))

can = True
for n in range(N):
    dist = abs(time_coor[n+1][1]-time_coor[n][1]) + \
           abs(time_coor[n+1][2]-time_coor[n][2])
    time = time_coor[n+1][0]-time_coor[n][0]
    if dist>time:
        can = False
        break
    elif dist%2==time%2:
        continue
    else:
        can = False
        break
    

if can==True:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 27324
import sys
sys.setrecursionlimit(1000000000)
def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod
def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod

x,y=map(int,input().split())
y,x=min(x,y),max(x,y)
if x>2*y or (x+y)%3!=0:
    #print(1)
    print(0)
else:
    print(comb((x+y)//3, min(x,y)-(x+y)//3,10**9+7))

Measured memory_bytes: 38512
# https://atcoder.jp/contests/abc104/tasks/abc104_c

import itertools
import collections
import bisect
import math

def main():
    D, G = map(int, input().split())
    p = []
    c = []
    for _ in range(D):
        pi, ci  = map(int, input().split())
        p.append(pi)
        c.append(ci)


    # big value
    INF = int(1e15)
    ans = INF
    # Bit 全探索
    pattern = 1 << D  # 1 をリストの長さだけ左にシフトする
    for i in range(pattern):
        scope = []
        for j in range(D):
            if (i >> j) & 1:
                scope.append(j)

        score = 0
        result = 0
        for s in scope:
            score += (s + 1) * p[s] * 100 + c[s]
            result += p[s]

        # print("i = {}, score = {}, result = {}".format(i, score, result))
        if score < G:
            for idx in range(D - 1, -1, -1):
                if idx not in scope:
                    rest = G - score
                    count = min(math.ceil(rest / ((idx + 1) * 100)), p[idx])
                    # print("idx = {}, count = {}".format(idx, count))
                    score += (idx + 1) * count * 100
                    result += count
                    break

        # print("i = {}, score = {}, result = {}".format(i, score, result))
        if score >= G:
            ans = min(ans, result)

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3316
import sys

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def main():
    n, c, k = MI()
    T = sorted([I() for _ in range(n)])
    cnt = 0
    i = 0
    while i < n:
        cnt += 1
        lim = T[i] + k
        cap = 1
        for j in range(i+1, min(n, i+c)):
            if T[j] <= lim:
                cap += 1
            else:
                break
        i += cap
    print(cnt)
if __name__ == '__main__':
    main()

Measured memory_bytes: 14040
#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() {
  long double n,a;
  long double ans=0;
  cin>>n;
  string b;
  rep(i,n){
   cin>>a>>b;
   if(b=="JPY"){
     ans+=a;
   }else{
     ans+=a*380000;
   }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/rope>
using namespace std;
using namespace chrono;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
mt19937 rng(high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rngll(high_resolution_clock::now().time_since_epoch().count());
template<typename T> T ctmax(T &x, const T &y){ return x = max(x, y); }
template<typename T> T ctmin(T &x, const T &y){ return x = min(x, y); }
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;



int main(){
	cin.tie(0)->sync_with_stdio(0);
	int n;
	string s;
	cin >> n >> s;
	vector<int> convert(128);
	convert['G'] = 1, convert['B'] = 2;
	vector<int> cnt(3);
	long long res = 0;
	for(auto j = 1; j < n; ++ j){
		++ cnt[convert[s[j - 1]]];
		for(auto k = j + 1; k < n; ++ k){
			if(s[j] != s[k]){
				res += j - cnt[convert[s[j]]] - cnt[convert[s[k]]] - (k <= 2 * j && s[2 * j - k] != s[j] && s[2 * j - k] != s[k]);
			}
		}
	}
	cout << res;
	return 0;
}

/*

*/

////////////////////////////////////////////////////////////////////////////////////////
//                                                                                    //
//                                   Coded by Aeren                                   //
//                                                                                    //
////////////////////////////////////////////////////////////////////////////////////////

Measured memory_bytes: 3648
import sys
import math

N = int(sys.stdin.readline().rstrip())

ans = float("inf")
d_max = int(math.sqrt(N))
for i in range(1, d_max+1):
    if N % i == 0:
        ans = min(ans, max(len(str(i)), len(str(N//i))))

print(ans)

Measured memory_bytes: 38768
from collections import Counter
n = int(input())
a = sorted([int(i) for i in input().split()])
c = Counter(a)
d =[]
for k,v in c.items():
    d.append([k,v])

    

def count(a):
    na = len(a)
    count = 0
    cmax = 0
    if n == 1:
        return 1
    else:
        for i in range(na):
            j = i
            while j <= na-1  and a[j][0]-a[i][0] <= 2:
                count += a[j][1]
                j += 1
            if count > cmax:
                cmax = count
            count = 0
        return cmax

print(count(d))


Measured memory_bytes: 16848
N = int(input())
A = list(map(int, input().split()))
cun =0
for i in range(N):
        if i == N-1:
            break
        elif A[i] > A[i+1]:
            cun += A[i] - A[i+1]
            A[i+1] = A[i]
        else:
            pass
print(cun)

Measured memory_bytes: 105108
#include<bits/stdc++.h>
const int N=200005;
using namespace std;
int n,a[N],sx[N],sy[N],t,mi,ans;
bool chk(){
	t=0;
	for(int i=1;i<n;i++)
	if(a[i]<=a[i-1]){
		for(;t&&sx[t]>a[i];t--);
		for(int j=a[i];j;j--,t--)
		if(sx[t]==j){
			if(++sy[t]<mi)break;
		}else{sx[++t]=j,sy[t]=1;break;}
		if(sy[t]>=mi||!t)return 0;
	}return 1;
}
int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	scanf("%d",a+i);
	for(int l=1,r=n;l<=r;){
		mi=l+r>>1;
		chk()?ans=mi,r=mi-1:l=mi+1;
	}printf("%d",ans);
}

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

int main() {
    string s,t;
    cin>>s>>t;
    int ns = s.length();
  bool f=0;
  for(int i=0;i<ns;i++){
  	if(s[i]!=t[i]){
    	f=1;
      	break;
    }
  }
    if(!f){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
	return 0;
}

Measured memory_bytes: 3596
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
//const int INF = 1e8;
using namespace std;

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

	if(k <= a){
		cout << 1 << endl;
		return 0;
	}

	if(a <= b){
		cout << -1 << endl;
	}else{
		long long ans = 1;
		k -= a;
		if(k % (a - b)) ans += 2;
		ans += k / (a - b) * 2;

		cout << ans << endl;
	}
}


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

int stoi(string s){
	int res=0;
	for(int i=0;i<s.size();i++){
		res*=10;
		res+=(s[i]-'0');
	}
	return res;
}

int main(){
	
	for(string s;cin>>s;){
		s="0"+s;
		int ans=0;
		for(int i=1;i<s.size();i++){
			string a=s.substr(0,i);
			string b=s.substr(i);
			if(b[0]=='0')continue;
			if((a[a.size()-1]-'0'+b[b.size()-1]-'0')%2==0){
				int c=(stoi(a)+stoi(b))/2;
				int d=c-+stoi(a);
				if(c>=0 && d>=0)ans++;
			}
		}
		cout<<ans<<endl;
	}
	
	return 0;
}


Measured memory_bytes: 1196
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;


int main()
{
    ll n, m, x, y;
    cin >> n >> m >> x >> y;
    vll vec_x(n);
    vll vec_y(m);
    REP(i, n) cin >> vec_x.at(i);
    REP(i, m) cin >> vec_y.at(i);
    sort(ALL(vec_x));
    reverse(ALL(vec_x));
    sort(ALL(vec_y));

    for(ll z = x + 1; z <= y; z++) {
        if (z > vec_x.at(0) && z <= vec_y.at(0)) {
            cout << "No War" << endl;
            return 0;
        }
    }
    cout << "War" << endl;
    return 0;
}

Measured memory_bytes: 256
n = int(input())
l = list(map(int,input().split()))
left = 0
right = 1
cou = 0
f = 2
while right!=n and right!=n+1:
  if l[left]==l[right]:
    left += 1
    right += 1
  elif l[left]<l[right]:
    while right!=n and l[left]<=l[right]:
      left += 1
      right += 1
    cou += 1
    left +=1
    right += 1
    f = 1
  else:
    while right!=n and l[left]>=l[right]:
      left += 1
      right += 1
    cou += 1
    left += 1
    right += 1
    f = 0
if f==2:
  cou += 1
elif f==1 and l[-2]>l[-1]:
  cou += 1
elif f==0 and l[-2]<l[-1]:
  cou += 1
print(cou)

Measured memory_bytes: 14480
#include<iostream>
#include<queue>
using namespace std;
struct node
{
    string name;
    int w;
    node (string s,int w):w(w),name(s){}
};
queue<node>que;
int main()
{
    int n,q;
    cin>>n>>q;
    for(int i=0;i<n;i++)
    {
        string s;int a;
        cin>>s>>a;
        que.push({s,a});
    }
    int ans=0;
    while(!que.empty())
    {
        if(que.front().w>q)
            que.push({que.front().name,que.front().w-q}),que.pop(),ans+=q;
        else
        {
            ans+=que.front().w;
            cout<<que.front().name<<' '<<ans<<endl;
            que.pop();
        }
    }
    return 0;
}



Measured memory_bytes: 6220
#include<bits/stdc++.h>
using namespace std;
int a[100005];
int dp[100005][50];
int main(){
    int n;
    scanf("%d",&n);
    for(int i = 1;i <= n;i++)
        scanf("%d",&a[i]);
    int L,Q;
    scanf("%d%d",&L,&Q);
    for(int i = 1;i <= n;i++){
        int id = upper_bound(a+1,a+1+n,a[i]+L)-a-1;
        if(a[i] + L >= a[n])
            dp[i][0] = n;
        else dp[i][0] = id;}
    for(int i = 1;i <= 30;i++){
        for(int j = 1;j <= n;j++)
            dp[j][i] = dp[dp[j][i-1]][i-1];}
    while(Q--){
        int L,R;
        scanf("%d%d",&L,&R);
        if(R<L)
            swap(L,R);  
        long long ans=0;
        for(int i = 30;i >= 0;i--){
            if(dp[L][i] < R){
                ans=ans+(1ll<<i);
                L=dp[L][i];}}printf("%lld\n",ans+1);}
    return 0;
}

Measured memory_bytes: 20736
#include <bits/stdc++.h>
using namespace std;
int m , n , i , j , k , a , b , c , s;
int main(){
	scanf("%d\n%d%d" , &k , &a , &b);
	for(i = a; i <= b; i ++){
		if(i % k == 0) s = 1;
	}
	if(s == 1) printf("OK");
	else printf("NG");
	return 0;
}

Measured memory_bytes: 3752
'use strict'

const Main = (input) => {
  const nr = input.split('\n')
  const N = parseInt(nr[0])
  let answer = 0
  for (let i = 0; i < N; i++) {
    const a = parseInt(nr[1].split(' ')[i])
    if ((a % 2 === 0) && ((a % 3 !== 0) && (a % 5 !== 0))) {
      answer = 1
      break
    }
  }
  if (answer === 0) {
    console.log('APPROVED')
  } else {
    console.log('DENIED')
  }
}

Main(require('fs').readFileSync('/dev/stdin', 'utf8'))


Measured memory_bytes: 11468
import java.util.Scanner;
 
public class Main {
  public static void main(String[] args){
  Scanner scan = new Scanner(System.in);
   
  
  int a = scan.nextInt();
  int b = scan.nextInt();
  int h = scan.nextInt();
  scan.close();
  	
  	System.out.println(((a + b) * h)/2);
 }
}

Measured memory_bytes: 21588
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Math;

class MainClass : Scanner
{
    static int N;
    static long[] A;
    static void Main()
    {
        N = RInt();
        A = RLongs();

        var B = new long[N];
        for (int i = 0; i < N; i++)
        {
            B[i] = A[i] - (i + 1);
        }
        Array.Sort(B);
        long b = B[N / 2];
        long ans = 0;
        for (int i = 0; i < N; i++)
        {
            ans += Abs(A[i] - (b + i + 1));
        }
        WriteLine(ans);
    }
}



class Scanner
{
    public static string RString() => Console.ReadLine();
    public static int RInt() => ReadTuple<int>();
    public static long RLong() => ReadTuple<long>();
    public static double RDouble() => ReadTuple<double>();

    public static string[] RStrings() => Console.ReadLine().Split();
    public static int[] RInts() => Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
    public static long[] RLongs() => Array.ConvertAll(Console.ReadLine().Split(), long.Parse);
    public static double[] RDoubles() => Array.ConvertAll(Console.ReadLine().Split(), double.Parse);
    public static int[] RInts(Func<string, int> func) => Console.ReadLine().Split().Select(func).ToArray();
    public static long[] RLongs(Func<string, long> func) => Console.ReadLine().Split().Select(func).ToArray();
    public static double[] RDoubles(Func<string, double> func) => Console.ReadLine().Split().Select(func).ToArray();
    //public static string[] RStrings(Func<string, string> func) => Console.ReadLine().Split().Select(func).ToArray();

    public static T1 ReadTuple<T1>()
    {
        var r = RString();
        var r1 = (T1)Convert.ChangeType(r, typeof(T1));
        return r1;
    }
    public static (T1, T2) ReadTuple<T1, T2>()
    {
        var r = RStrings();
        var r1 = (T1)Convert.ChangeType(r[0], typeof(T1));
        var r2 = (T2)Convert.ChangeType(r[1], typeof(T2));
        return (r1, r2);
    }
    public static (T1, T2, T3) ReadTuple<T1, T2, T3>()
    {
        var r = RStrings();
        var r1 = (T1)Convert.ChangeType(r[0], typeof(T1));
        var r2 = (T2)Convert.ChangeType(r[1], typeof(T2));
        var r3 = (T3)Convert.ChangeType(r[2], typeof(T3));
        return (r1, r2, r3);
    }
    public static (T1, T2, T3, T4) ReadTuple<T1, T2, T3, T4>()
    {
        var r = RStrings();
        var r1 = (T1)Convert.ChangeType(r[0], typeof(T1));
        var r2 = (T2)Convert.ChangeType(r[1], typeof(T2));
        var r3 = (T3)Convert.ChangeType(r[2], typeof(T3));
        var r4 = (T4)Convert.ChangeType(r[3], typeof(T4));
        return (r1, r2, r3, r4);
    }
}


Measured memory_bytes: 46816
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (k); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
#define D10 fixed<<setprecision(10)
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
const int MOD = 1000000007;
const ll INF = MOD + 1;
const ld EPS = 1e-10;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }

/*--------------------template--------------------*/
int p[50], t[50], dp[50][5];
int n;

int solve(int i, int j)
{
	if (i == n) return p[n];
	if (dp[i][j] >= 0) return dp[i][j];
	int res = INF;
	if (p[i] * (j + 1) + p[i + 1] <= t[i + 1] - t[i]) 
		chmin(res, solve(i + 1, 1) + p[i] + p[i + 1]);
	if (j < 3 && abs(p[i] - p[i + 1]) * (j + 1) <= t[i + 1] - t[i]) 
		chmin(res, solve(i + 1, j + 1) + abs(p[i] - p[i + 1]));
	return dp[i][j] = res;
}

int main()
{
	while (cin >> n, n)
	{
		MS(dp, -1);
		FOR(i, 1, n + 1) cin >> p[i] >> t[i];
		int ans = solve(0, 0);
		if (ans == INF)
		{
			while (ans == INF)
			{
				MS(dp, -1);
				n--;
				ans = solve(0, 0);
			}
			cout << "NG " << n+1 << endl;
		}
		else cout << "OK " << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 1160
#define LL long long
#include<cstdio>
using namespace std;
LL a,b;
LL gcd(LL x,LL y)
{
	return y?gcd(y,x%y):x;
}
int main()
{
	scanf("%lld%lld",&a,&b);
	printf("%lld",a*b/gcd(a,b));
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define inf (ll)1e9
#define mod (ll)(1e9+7)
#define d(x) cerr<<#x<<"="<<x<<endl;
#define p(x) cout<<(x)<<endl
#define ps(x) cout<<(x);
#define pk(x) cout<<(x)<<" ";
#define pfix(d,x) cout << fixed << setprecision(d) << x << endl;
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define minel(v) *min_element(all(v))
#define minind(v) distance((v).begin(), min_element(all(v)))
#define maxel(v) *max_element(all(v))
#define maxind(v) distance((v).begin(), max_element(all(v)))
#define fi first
#define se second
ll a[100001],b[100001],c[100001],d,n,m,x,y,z,h,w,k,sum,mi=inf,ma=-inf,ans,s,t,l,r,res,tmp,itr,p,q;
bool flag;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int dx8[8]={1,1,0,-1,-1,-1,0,1},dy8[8]={0,1,1,1,0,-1,-1,-1};
char cha;
string st;
typedef map<ll, ll> imap;
typedef pair<ll, ll> P;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<pair<ll,ll> > VP;
string S[100001];

int main(void){
    cin>>n>>m;
    rep(i,m){
        cin>>b[i]>>S[i];
        if(S[i]=="WA" && a[b[i]]==0){
            c[b[i]]++;
        }
        if(S[i]=="AC"){
            a[b[i]]=1;
        }
    }
    ll num_ans=0, num_pe=0;
    rep(i,n+1){
        if(a[i]==1){
            num_ans++;
            num_pe+=c[i];
        }
    }
    cout<<num_ans<<" "<<num_pe<<endl;
    return 0;
}


Measured memory_bytes: 7936
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bits/stdc++.h>
#include<cmath>
#include<bitset>
#include<queue>
#define ll long long
#define itn int
#define co(ans) cout<<ans<<endl;
#define COYE cout<<"YES"<<endl;
#define COYe cout<<"Yes"<<endl;
#define COye cout<<"yes"<<endl;
#define CONO cout<<"NO"<<endl;
#define CONo cout<<"No"<<endl;
#define COno cout<<"no"<<endl;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n)  FFOR(i,1,n)
#define SORT(V) sort((V).begin(),(V).end())
#define REVERSE(V) reverse((V).begin(),(V).end())
#define INF ((1LL<<62)-(1LL<<31))
#define MOD 1000000007
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
using namespace std;


int main(){
  int N,M;
  cin>>N>>M;
  
  int S[M],C[M];
  REP(i,M) cin>>S[i]>>C[i];
  
  int L[N+1];
  bool P[N+1],CAN=true;
  REP(i,N+1){
    L[i]=0;
    P[i]=false;
  }
  
  REP(i,M){
    if(P[S[i]]==false||(P[S[i]]==true&&L[S[i]]==C[i])){
      P[S[i]]=true;
      L[S[i]]=C[i];
    }
    else{
      CAN=false;
    }
  }
  
  if(L[1]==0&&P[1]==true) CAN=false;
  
  bool Q=true;
  for(int i=1; i<=N; ++i){
    
    if(L[i]!=0) Q=false;
    
  }
  if(Q) CAN=true;
  
  if(P[1]==false&&N>1){
    L[1]=1;
  }
  
  
  if(N>=2){
    bool R=true;
    for(int i=1; i<=N; ++i){
      if(L[i]!=0) R=false;
    }
    if(R) CAN=false;
  }
  
  
  if(CAN){
    for(int i=1; i<=N; ++i) cout<<L[i];
    cout<<endl;
  }
  else cout<<-1<<endl;
  
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.UncheckedIOException;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) {
		SC sc = new SC(System.in);
		int N=sc.nextInt();
		int[] time=new int[N];
		for(int i=0; i<N; i++) {
			time[i]=sc.nextInt()*2;
			if(i>0) {
				time[i]+=time[i-1];
			}
		}
		int[] v=new int[N];
		for(int i=0; i<N; i++) {
			v[i]=sc.nextInt()*2;
		}
		int[][] speedlimit=new int[N][time[N-1]+1];
		int[] skd=new int[time[N-1]+1];
		for(int i=0; i<N-1; i++) {
			Arrays.fill(speedlimit[i], 0);
		}
		for(int i=time[N-1]; i>=0; i--) {
			speedlimit[N-1][i]=time[N-1]-i;
		}
		Arrays.fill(skd, 0);
		for(int i=0; i<N; i++) {
			skd[time[i]]=v[i];
		}
		for(int i=time[N-1]; i>=0; i--) {
			if(skd[i]>0) {
				//
			}
			else {
				skd[i]=skd[i+1];
			}
		}
		for(int i=1; i<N; i++) {
			speedlimit[i-1][time[i-1]]=v[i];
		}
		for(int i=0; i<N-1; i++) {
			for(int j=time[i]; j>=0; j--) {
				speedlimit[i][j]=speedlimit[i][time[i]]+Math.abs(time[i]-j);
			}
			for(int j=time[i]+1; j<time[N-1]+1; j++) {
				speedlimit[i][j]=114514810;
			}
		}
		/*for(int i=0; i<N; i++) {
			for(int j=0; j<time[N-1]+1; j++) {
				p(speedlimit[i][j]+" ");
			}
			pl();
		}
		for(int i=0; i<time[N-1]+1; i++) {
			p(skd[i]+" ");
		}*/
		int[] s=new int[time[N-1]+1];
		s[0]=0;
		for(int i=1; i<=time[N-1]; i++) {
			int max=114514810;
			for(int j=0; j<N; j++) {
				max=Math.min(max, speedlimit[j][i]);
			}
			max=Math.min(max, skd[i]);
			if(s[i-1]+1<=max) {
				s[i]=s[i-1]+1;
			}
			else if(s[i-1]==max) {
				s[i]=s[i-1];
			}
			else {
				s[i]=s[i-1]-1;
			}
		}
		int sum=0;
		for(int i=1; i<=time[N-1]; i++) {
			sum+=s[i-1]+s[i];
		}
		/*for(int i=0; i<time[N-1]; i++) {
			p(s[i]+" ");
		}
		pl();
		pl(sum);*/
		pl(((double)sum)/8);
	}
	static class SC {
		private BufferedReader reader = null;
		private StringTokenizer tokenizer = null;
		public SC(InputStream in) {
			reader = new BufferedReader(new InputStreamReader(in));
		}
		public String next() {
			if (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new UncheckedIOException(e);
				}
			}
			return tokenizer.nextToken();
		}
		public int nextInt() {
			return Integer.parseInt(next());
		}
		public long nextLong() {
			return Long.parseLong(next());
		}
		public double nextDouble() {
			return Double.parseDouble(next());
		}
		public String nextLine() {
			try {
				return reader.readLine();
			} catch (IOException e) {
				throw new UncheckedIOException(e);
			}
		}
	}
	public static void pl(Object o) {
		System.out.println(o);
	}
	public static void pl() {
		System.out.println();
	}
	public static void p(Object o) {
		System.out.print(o);
	}
}

Measured memory_bytes: 50724
n = int(input())
a = [-int(i) for i in input().split()]


class SparseTable:
    def __init__(self, a, func=max, one=-10**18):
        self.table = [a[:]]
        self.n = len(a)
        self.logn = self.n.bit_length()
        self.func = func
        self.one = one

        for i in map(lambda x: 1 << x, range(self.logn - 1)):
            self.table.append([])
            for j in range(self.n - i * 2 + 1):
                self.table[-1].append(self.func(self.table[-2][j],
                                                self.table[-2][j + i]))

    def get_section(self, i, j):
        length = j - i
        log = length.bit_length() - 1
        if length <= 0:
            return self.one
        return self.func(self.table[log][i], self.table[log][j - (1 << log)])


sp = SparseTable(a)
ans = 0
for i in range(n):
    mi = 0
    ma = i
    while mi != ma:
        mm = (mi + ma) // 2
        if sp.get_section(mm, i) <= a[i]:
            ma = mm
        else:
            mi = mm + 1
    j = i - mi + 1

    mi = i - 1
    ma = n - 1
    while mi != ma:
        mm = (mi + ma) // 2 + 1
        if sp.get_section(i, mm + 1) <= a[i]:
            mi = mm
        else:
            ma = mm - 1
    k = mi - i + 1
    ans += j * k * a[i]
print(-ans)


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

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

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

    cout << (d[N/2] - d[N/2-1]) << endl;
    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <cstdio>
#include <set>
#include <list>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <string>
#include <sstream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <fstream>
#include <iomanip>
#include <unordered_map>
using namespace std;
#define dbg(x) cerr << #x " = " << x << endl;
typedef pair<int, int> P;
typedef long long ll;
string a[105];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, l;
    cin >> n >> l;
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    sort(a, a+n);
    for(int i = 0; i < n; i++)
    {
        cout << a[i];
    }
    return 0;
}

Measured memory_bytes: 256
use std::io::{stdin, Read, StdinLock};
use std::str::FromStr;

fn main() {
    let cin = stdin();
    let mut scan = Scanner::new(cin.lock());
    let x = scan.read::<i64>();
    let n = 1000000i64;
    let mut is_ok = false;
    'outer: for a in 0..n {
        let mut rest = x - a*100;
        if rest == 0 {is_ok=true;break 'outer;}
        if rest < 0 {break;}
        for b in 0..n {
            rest = x - a*100 - b*101;
            if rest == 0 {is_ok=true;break 'outer;}
            if rest < 0 {break;}
            for c in 0..n {
                rest = x - a*100 - b*101 - c*102;
                if rest == 0 {is_ok=true;break 'outer;}
                if rest < 0 {break;}
                for d in 0..n {
                    rest = x - a*100 - b*101 - c*102 - d*103;
                    if rest == 0 {is_ok=true;break 'outer;}
                    if rest < 0 {break;}
                    for e in 0..n {
                        rest = x - a*100 - b*101 - c*102 - d*103 - e*104;
                        if rest == 0 {is_ok=true;break 'outer;}
                        if rest < 0 {break;}
                        for f in 0..n {
                            rest = x - a*100 - b*101 - c*102 - d*103 - e*104 - f*105;
                            if rest == 0 {is_ok=true;break 'outer;}
                            if rest < 0 {break;}
                        }
                    }
                }
            }
        }
    }
    println!("{}", if is_ok {1} else {0});
}

// region template
#[allow(dead_code)]
fn iu(i: i64) -> usize { i as usize }

#[allow(dead_code)]
fn ui(i: usize) -> i64 { i as i64 }

#[allow(dead_code, deprecated)]
fn join<T: std::fmt::Display>(slice: &[T], sep: &str) -> String {
    let strings = slice.iter().map(|t| format!("{}", t)).collect::<Vec<_>>();
    strings.connect(sep)
}

#[allow(dead_code)]
fn arr<'a, S, T>(n: usize, mut f: S) -> Vec<T> where S: FnMut(usize) -> T + 'a {
    (0..n).map(|i| f(i)).collect::<Vec<T>>()
}

struct Scanner<'a> {
    cin: StdinLock<'a>,
}

#[allow(dead_code)]
impl<'a> Scanner<'a> {
    fn new(cin: StdinLock<'a>) -> Scanner<'a> {
        Scanner { cin: cin }
    }

    fn read1<T: FromStr>(&mut self) -> Option<T> {
        let token = self.cin.by_ref().bytes().map(|c| c.unwrap() as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect::<String>();
        token.parse::<T>().ok()
    }

    fn read<T: FromStr>(&mut self) -> T {
        self.read1().unwrap()
    }

    fn readn<T: FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read::<T>()).collect()
    }

    fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}
// endregion

Measured memory_bytes: 4352
N=int(input())
A=list(map(int,input().split()))
n=sum(list(map(int,input().split())))
C=list(map(int,input().split()))
C.append(0)
for i in range(N-1):
  if A[i+1]==A[i]+1:
    n+=C[A[i]-1]
print(n)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define REP(i, e) for(int (i) = 0; (i) < (e); ++(i))
#define FOR(i, b, e) for(int (i) = (b); (i) < (e); ++(i))
#define ALL(c) (c).begin(), (c).end()
#define PRINT(x) cout << (x) << "\n"
using namespace std;
using ll = long long; using pint = pair<int, int>; using pll = pair<ll, ll>;
template<typename T> auto compare = [](T x, T y) -> bool{return (x < y);};
const int MOD = 1000000007;

signed main(){
    int N;
    string S;
    map<string, int> mp;
    cin >> N;
    REP(i, N){
        cin >> S;
        mp[S]++;
    }
    cout << "AC x " << mp["AC"] << endl;
    cout << "WA x " << mp["WA"] << endl;
    cout << "TLE x " << mp["TLE"] << endl;
    cout << "RE x " << mp["RE"] << endl;
    return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
#define all(x) (x).begin(), (x).end()
#define fsp(x) fixed << setprecision(x)
const ll inf = LLONG_MAX;
const long double pi = acos(-1);
void Yes() {cout << "Yes" << endl;}
void No() {cout << "No" << endl;}
void YES() {cout << "YES" << endl;}
void NO() {cout << "NO" << endl;}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	//const ll p = 1e9 + 7;
	//const ll p = 998244353;

	string s;
	cin >> s;
	if (s == "AAA" || s == "BBB") No();
	else Yes();
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
int main( void )
{
  long int a, b, c, d;
  cin >> a >> b >> c >> d;
  long long int max = -9223372036854775807;
 
  if( max < a * c )
    max = a * c;
  if( max < a * d )
    max = a * d;
  if( max < b * c )
    max = b * c;
  if( max < b * d )
    max = b * d;
 
  cout << max << endl;
  
}

Measured memory_bytes: 3652
/*~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=
*$* WRITER:kakitamasziru/OxOmisosiru *$*
~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=*/
#ifdef LOCAL_JUDGE
#define _GLIBCXX_DEBUG //FOR THE DEBUG! COMMENT OUT THIS WHEN SUBMITTING!
#endif
/* I REALLY HOPE MY WISH REACH YOU , ATCODER'S ONLINE JUDGE */
#define WOULD
#define YOU
#define PLEASE
#define ACCEPT
#define MY
#define SUBMISSION
/* I REALLY HOPE MY WISH REACH YOU , ATCODER'S ONLINE JUDGE */
#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 <stack> // stack
#include <deque> // deque
#include <math.h>//pow,,,
#include <cmath>//abs,,,
#include <bitset> // bitset
//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 = 100100100100;
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;
}

long long 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 * b / gcd(a, b);
}

int main() {
    long long A,B,C;cin >> A >> B >> C;
    if(A == B && B == C && A == C && A % 2 == 0 && B % 2 == 0 && C % 2 == 0){
        cout << -1 << endl;
        return 0;
    }
    int count = 0;
    while(true){
        long long a,b,c;
        if(A % 2 == 1 || B % 2 == 1 || C % 2 == 1) break;
        a = A/2;
        b = B/2;
        c = C/2;
        A = 0;B = 0;C = 0;
        A = b+c;
        B = a+c;
        C = a+b;
        count++;
    }
    cout << count << endl;

}

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

using namespace std;
using ll = long long;
// #define int ll
using PII = pair<ll, ll>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()

template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) {
    return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a) {
    out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
    out<<'[';
    for(const T &i: a) out<<i<<',';
    out<<']';
    return out;
}
template<class T>
ostream &operator <<(ostream& out, const set<T>& a) {
    out<<'{';
    for(const T &i: a) out<<i<<',';
    out<<'}';
    return out;
}
template<class T, class S>
ostream &operator <<(ostream& out, const map<T,S>& a) {
    out<<'{';
    for(auto &i: a) out<<i<<',';
    out<<'}';
    return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;

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

    ll n, m;
    cin >> n >> m;
    vector<vector<ll>> v(m);
    REP(i, m) {
        ll k;
        cin >> k;
        REP(j, k) {
            ll s;
            cin >> s;
            s--;
            v[i].push_back(s);
        }
    }
    vector<ll> p(m);
    REP(i, m) cin >> p[i];

    ll ret = 0;
    REP(i, 1LL<<n) {
        bool flag = true;
        REP(j, m) {
            ll cnt = 0;
            for(auto k: v[j]) {
                if(i&1LL<<k) {
                    cnt++;
                }
            }
            if(cnt%2 != p[j]) {
                flag = false;
            }
        }
        if(flag) ret++;
    }
    cout << ret << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <utility>
#define EPS 1e-10
#define maxn 100005
using namespace std;
typedef long long ll;
//det < 0: Not-convex.
struct Point{
	double x,y;
	Point(double x = 0.0,double y = 0.0): x(x),y(y) {}
	Point operator + (Point p){
		return Point(x + p.x,y + p.y);
	}
	Point operator - (Point p){
		return Point(x - p.x,y - p.y);
	}
	Point operator * (double lambda){
		return Point(x * lambda,y * lambda);
	}
	Point operator / (double lambda){
		return Point(x / lambda,y / lambda);
	}
	double norm(){
		return x * x + y * y;
	}
	double abs_(){
		return sqrt(norm());
	}
	bool operator == (const Point &p)const
	{
		return abs(x - p.x) < EPS && abs(y - p.y) < EPS;
	}
	bool operator < (const Point &p)const
	{
		if(abs(x - p.x) < EPS) return y - p.y < -EPS;
		else return x - p.x < EPS;
	}
};
typedef Point Vector;
double dot(Vector a,Vector b){
	return a.x * b.x + a.y * b.y;
}
double det(Vector a,Vector b){
	return a.x * b.y - b.x * a.y;
}
int n,k;
Point ps[maxn],con[maxn<<1];
void convexHull(){//an 180-degree angle is considered as "convex".
	sort(ps + 1,ps + n + 1);
	for(int i=1;i<=n;i++){
		while(k > 1 && det(ps[i] - con[k],con[k - 1] - con[k]) < -EPS) k--;
		con[++k] = ps[i];
	}
	int t = k;
	for(int i=n-1;i>=1;i--){
		while(k > t && det(ps[i] - con[k],con[k - 1] - con[k]) < -EPS) k--;
		con[++k] = ps[i];
	}
	k--;
}
bool cmp(Point p1,Point p2){
	if(abs(p1.y - p2.y) < EPS) return p1.x < p2.x - EPS;
	return p1.y < p2.y - EPS;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%lf%lf",&ps[i].x,&ps[i].y);
	}
	convexHull();
	printf("%d\n",k);
	int minid = 0;
	for(int i=1;i<=k;i++){
		if(minid == 0 || cmp(con[i],con[minid])) minid = i;
	}
	for(int i=minid;i<=k;i++){
		printf("%.0f %.0f\n",con[i].x,con[i].y);
	}
	for(int i=1;i<minid;i++){
		printf("%.0f %.0f\n",con[i].x,con[i].y);
	}
	return 0;
}



Measured memory_bytes: 7940
#include <bits/stdc++.h>
#define FI first
#define SE second
#define PB push_back
#define ll long long
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ROF(i,a,b) for(int i=b-1;i>=a;i--)
#define YES(i) cout<<(i?"YES":"NO")<<endl
#define Yes(i) cout<<(i?"Yes":"No")<<endl
#define co(i) cout<<(i)<<endl
#define fcout cout<<fixed<<setprecision(10)
#define uni(i) i.erase(unique(i.begin(), i.end()), i.end());
#define all(i) i.begin(),i.end()
#define pint pair<int, int>
#define vint vector<int>
using namespace std;

const int INF=1e9+7;
const int MOD=1e9+7;
//const int MOD=998244353;

int main(){
	int x1,y1,x2,y2; cin>>x1>>y1>>x2>>y2;
	printf("%d %d %d %d\n",x2+y1-y2,y2+x2-x1,x1+y1-y2,y1+x2-x1);
}


Measured memory_bytes: 256
#define	_USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cfloat>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <string>
using namespace std;
int main(){
	
	int d,c;
	
	cin>>d>>c;
	
	cout<<d*c<<endl;
	

}

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

using namespace std;

#define FOR(i, a, b) for(ll i = (a); i < (b); ++i)
#define FORR(i, a, b) for(ll i = (a); i > (b); --i)
#define REP(i, n) for(ll i = 0; i < (n); ++i)
#define REPR(i, n) for(ll i = n; i >= 0; i--)
#define FOREACH(x, a) for(auto &(x) : (a))
#define VECCIN(x)                                                              \
    for(auto &youso_ : (x)) cin >> youso_
#define mp make_pair
#define bitcnt __builtin_popcount
#define SZ(x) ((ll)(x).size())
#define All(a) (a).begin(), (a).end()
template <typename T = long long> inline T IN() {
    T x;
    cin >> x;
    return (x);
}
inline void CIN() {}
template <class Head, class... Tail>
inline void CIN(Head &&head, Tail &&... tail) {
    cin >> head;
    CIN(move(tail)...);
}
#define CINT(...)                                                              \
    int __VA_ARGS__;                                                           \
    CIN(__VA_ARGS__)
#define LCIN(...)                                                              \
    ll __VA_ARGS__;                                                            \
    CIN(__VA_ARGS__)
#define SCIN(...)                                                              \
    string __VA_ARGS__;                                                        \
    CIN(__VA_ARGS__)
#define Yes(a) cout << (a ? "Yes" : "No") << "\n"
#define YES(a) cout << (a ? "YES" : "NO") << "\n"

typedef long long ll;
typedef unsigned long long ul;
typedef vector<int> V;
typedef vector<ll> VL;
typedef pair<ll, ll> PL;
typedef priority_queue<ll> PQ;
typedef priority_queue<ll, V, greater<ll>> PQG;

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

ll N, M;
VL P, ally;
vector<VL> Y;

int main() {
    cin >> N >> M;
    Y.resize(N + 1);
    REP(i, M) {
        LCIN(p, y);
        P.emplace_back(p);
        ally.emplace_back(y);
        Y[p].emplace_back(y);
    }
    REP(i, N + 1) sort(All(Y[i]));
    REP(i, M) {
        printf("%06d", P[i]);
        printf("%06d", lower_bound(All(Y[P[i]]), ally[i]) - Y[P[i]].begin() + 1);
        cout << "\n";
    }
}


Measured memory_bytes: 8552
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; (i) < (n); ++(i))
#define REP3(i,m,n) for (int i = (m); (i) < (n); ++(i))
#define REP_R(i,n) for (int i = (int)(n) - 1; (i) >= 0; --(i))
#define ALL(x) begin(x), end(x)
using namespace std;
using ll = long long;
template <class T> inline void chmin(T & a, T const & b) { a = min(a, b); }

vector<array<int, 2> > make_table(string const & s) {
    int n = s.length();
    vector<array<int, 2> > next(n + 2);
    next[n][0] = n;
    next[n][1] = n;
    next[n + 1][0] = n;
    next[n + 1][1] = n;
    REP_R (i, n) {
        next[i] = next[i + 1];
        next[i][s[i] - '0'] = i;
    }
    return next;
}

string solve(string const & p, string const & q) {
    auto next_p = make_table(p);
    auto next_q = make_table(q);

    // run dp based on greedy
    vector<vector<int> > dp(p.size() + 2, vector<int>(q.size() + 2, INT_MAX));
    dp[0][0] = 0;
    REP (i, p.size() + 2) {
        REP (j, q.size() + 2) if (dp[i][j] != INT_MAX) {
            REP (c, 2) {
                chmin(dp[next_p[i][c] + 1][next_q[j][c] + 1], dp[i][j] + 1);
            }
        }
    }

    // propagate the flag
    vector<vector<bool> > pred(p.size() + 2, vector<bool>(q.size() + 2, false));
    pred[p.size() + 1][q.size() + 1] = true;
    REP_R (i, p.size() + 2) {
        REP_R (j, q.size() + 2) if (dp[i][j] != INT_MAX) {
            REP (c, 2) {
                int ni = next_p[i][c] + 1;
                int nj = next_q[j][c] + 1;
                if (pred[ni][nj] and dp[ni][nj] == dp[i][j] + 1) {
                    pred[i][j] = true;
                }
            }
        }
    }
    assert (pred[0][0]);

/*
    REP (i, p.size() + 2) {
        REP (j, q.size() + 2) {
            if (dp[i][j] == INT_MAX) {
                cerr << ". ";
            } else if (pred[i][j]) {
                cerr << dp[i][j] << " ";
            } else {
                cerr << "(" << dp[i][j] << ") ";
            }
        }
        cerr << endl;
    }
*/

    // reconstruct
    string s;
    for (int i = 0, j = 0; i <= p.size() or j <= q.size(); ) {
        int c = 0;
        while (c < 2 and not (pred[next_p[i][c] + 1][next_q[j][c] + 1] and dp[next_p[i][c] + 1][next_q[j][c] + 1] == dp[i][j] + 1)) ++ c;
        assert (c != 2);
        s += c + '0';
        i = next_p[i][c] + 1;
        j = next_q[j][c] + 1;
// cerr << i << ' ' << j << " (" << dp[i][j] << endl;
    }
    
    return s;
}

int main() {
    string p, q; cin >> p >> q;
    cout << solve(p, q) << endl;
    return 0;
}



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

const int MAX = 2100;
const int MOD = 1000000007;

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

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

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

int main()
{
	int N, K;

	cin >> N >> K;

	COMinit();

	for( int i = 1; i <= K; i++ ) {
		long long ans = COM( N - K + 1, i ) * COM( K - 1, i - 1 );
		ans %= MOD;
		cout << ans << endl;
	}
}


Measured memory_bytes: 256