akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define res register int
#define ll long long
#define inf 0x3f3f3f3f
#define N 100050
using namespace std;
int a[N],n,m,l;
int main()
{
	scanf("%d%d",&n,&l);
	for(res i=1;i<=n;i++)
	scanf("%d",&a[i]);
		res j=1;
	for(res i=1;i<n;i++)
	if(a[i]+a[i+1]>a[j]+a[j+1]) j=i;
	if(a[j]+a[j+1]<l)
	printf("Impossible");
	else
	{
		printf("Possible\n");
		for(res i=n-1;i>j;i--)
		printf("%d\n",i);
		for(res i=1;i<=j;i++)
		printf("%d\n",i);
	}
} 


Measured memory_bytes: 1152
#exec({'RUBY_THREAD_VM_STACK_SIZE'=>'100000000'},'/usr/bin/ruby', $0) if !ENV['RUBY_THREAD_VM_STACK_SIZE']

def inpf() a=gets.chomp.split(" ").map(&:to_f)end

def inps() a=gets.chomp.split(" ")end

def copy(a) Marshal.load(Marshal.dump(a)) end

def kaijo(n,r = 10**9+7)(n < 2)? 1 : (2..n).inject{|memo,u|memo=(memo*u)%r} end

def na(n,d=0) Array.new(n,d)end

def na2(n,m,d=0) Array.new(n){Array.new(m,d)}end

def na3(n,m,l,d=0) Array.new(n){Array.new(m){Array.new(l,d)}}end

def inp() a=gets.chomp.split(" ").map(&:to_i)end

def r_up(a, b) (a+b-1)/b end

def r_sort(a) a.sort{|a,b|b<=>a} end

n =inp[0]
t = []
n.times do
  t.push(inp[0])
end
max = t.sort()[-1]
max2 = t.sort[-2]
t.each do |d|
  puts (d==max)? max2:max
end

Measured memory_bytes: 8040
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <iomanip>
#include <set>
#include <ctime>
#include <tuple>
#include <bitset>
#include <assert.h>
#include <deque>
#include <functional>
using namespace std;
typedef long long ll;

#define fi first
#define se second
#define rep(i, n) for (ll i = 0; i < n; i++)
#define debugA cerr << "AAAAA" << endl
#define debug_ cerr << "-------------" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define debug_vec(v)                   \
    cout << #v << endl;                \
    for (int i = 0; i < v.size(); i++) \
    {                                  \
        cout << v[i] << " ";           \
    }                                  \
    cout << endl;
#define debug_vec2(v)                         \
    cout << #v << endl;                       \
    for (int i = 0; i < v.size(); i++)        \
    {                                         \
        for (int j = 0; j < v[i].size(); j++) \
        {                                     \
            cout << v[i][j] << " ";           \
        }                                     \
        cout << endl;                         \
    }

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

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

template <typename T>
void quit(T a)
{
    cout << a << endl;
    exit(0);
}

using Graph = vector<vector<int>>;
using P = pair<int, int>;
using P1 = pair<int, pair<int, int>>; // クラスカル法とかで、{cost, {from, to}}的に使う。
const ll LINF = 10010020030040056ll;
const int INF = 1001001001;
const double pi = acos(-1);

void MergeSort(vector<int> &a, int left, int right)
{
    if (right - left == 1)
        return;

    int mid = (right + left) / 2;
    MergeSort(a, left, mid);
    MergeSort(a, mid, right);
    int i = left;
    int j = mid;
    vector<int> tmp;
    while (true)
    {
        if (i == mid && j == right)
        {
            break;
        }
        else if (i == mid)
        {
            tmp.push_back(a.at(j));
            j++;
            continue;
        }
        else if (j == right)
        {
            tmp.push_back(a.at(i));
            i++;
            continue;
        }
        if (a[i] <= a[j])
        {
            tmp.push_back(a.at(i));
            i++;
        }
        else
        {
            tmp.push_back(a.at(j));
            j++;
        }
    }
    for (int i1 = left; i1 < right; i1++)
    {
        a.at(i1) = tmp.at(i1 - left);
    }
}

int main()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    int ans = 0;
    int cntr = 0;
    for (int i = 0; i < n; i++)
    {
        if (s[i] == 'R')
        {
            cntr++;
        }
    }
    for (int i = 0; i < cntr; i++)
    {
        if (s[i] == 'W')
        {
            ans++;
        }
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3732
#include <bits/stdc++.h>
using namespace std;
int N, K;
vector<vector<int>> G;
int rr;
vector<bool> a;
int pos, dist;
void f(int p, int q, int k) {
	if (k > K) { a[p] = false; rr ++; }
	else if (k > dist) { pos = p; dist = k; }
	for (int x : G[p]) if (x != q) {
		f(x, p, k+1);
	}
}
void g(int p, int q, int k) {
	if (k > K) { rr ++; }
	for (int x : G[p]) if (x != q && a[x]) {
		g(x, p, k+1);
	}
}
int main() {
	cin >> N >> K;
	G.resize(N);
	for (int i = 0; i < N-1; ++ i) {
		int a, b;
		cin >> a >> b;
		-- a; -- b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	int r = 1<<30;
	for (int i = 0; i < N; ++ i) {
		rr = 0;
		a = vector<bool>(N, true);
		pos = -1;
		dist = -1;
		f(i, -1, 0);
		g(pos, -1, 0);
		r = min(rr, r);
	}
	cout << r << endl;
}


Measured memory_bytes: 384
//#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"

#define rep(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007
typedef long long ll;

using namespace std;


int main() {
	ll h, w; cin >> h >> w;
	ll n; cin >> n;
	vector<vector<ll>> v(h, vector<ll>(w));
	vector<ll> color(n);
	rep(i, n) cin >> color[i];
	ll cn = 0;
	rep(i,h)
		rep(j, w) {
		if (color[cn] == 0) cn += 1;
		color[cn] -= 1;
		if (i % 2 == 0) v[i][j] = cn + 1;
		else v[i][w - 1 - j] = cn + 1;
	}
	rep(i,h)
		rep(j, w) {
		cout << v[i][j];
		if (j < w - 1) cout << " ";
		else cout << endl;
	}
}

Measured memory_bytes: 512
#include <stdio.h>

void	ft_swap(long *a, long *b)
{
	long tmp;

	tmp = *a;
	*a = *b;
	*b = tmp;
}

void	ft_quick_sort(long *d, long left, long right)
{
	long Left, Right;
	long pivot;

	Left = left, Right = right;
	pivot = d[(left + right) / 2];

	//昇順ソートの場合
	while (1)
	{
		//pivot(基準)より小さい場合進んでpivotより大きい値の要素を探す
		while (d[Left] < pivot)
			Left++;
		//pivot(基準)より大きい場合進んでpivotより小さい値の要素を探す
		while (d[Right] > pivot)
			Right--;
		if (Left >= Right)
			break;
		//d[Left]の、基準より大きい値と d[Right]の基準より小さい値を入れ替え
		ft_swap(&d[Left], &d[Right]);
		Left++; Right--;
	}
	// 左のデータ群を対象としてクイックソートを再帰
	// left から (Left - 1) まで探索
	if (left < Left - 1)
		ft_quick_sort(d, left, Left - 1);
	// 右のデータを対象としてクイックソートを開始
	// right から (Right - 1)まで探索
	if (Right + 1 < right)
		ft_quick_sort(d, Right + 1, right);
}

int		main(void)
{
	long n;
	scanf("%ld", &n);
	long d[n + 1];
	long i = 0;
	while (i < n)
		scanf("%ld", &d[i++]);
	ft_quick_sort(d, 0, n - 1);
	i = 0;
	// while (i < n)
	// 	printf("%ld ", d[i++]);
	long abc,arc;
	arc = d[(n / 2)];
	abc = d[n / 2 - 1];
	printf("%ld", arc - abc);
	return (0);
}


Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
main(){
  int64_t i;
  int64_t n;cin >> n;
  vector<int64_t> a(n);for(int i=0;i<n;i++) cin >> a[i];
  int64_t sum=0,ans0=0,ans1=0;
  
  for(i=0;i<n;i++){
    sum += a[i];
    if(i%2==0 && sum<=0){
      ans0 += abs(sum) +1;
      sum = 1;
    } else if(i%2==1 && sum>=0){
      ans0 += abs(sum) +1;
      sum = -1;
    }
  }
  
  sum=0;

  for(i=0;i<n;i++){
    sum += a[i];
    if(i%2==0 && sum>=0){
      ans1 += abs(sum) +1;
      sum = -1;
    } else if(i%2==1 && sum<=0){
      ans1 += abs(sum) +1;
      sum = 1;
    }
  }
  
  cout << min(ans0,ans1) << endl;
  return 0;
}

Measured memory_bytes: 4012
#include<bits/stdc++.h>
#define N 100005
using namespace std;
int n;
int a[N];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	int ans=0;
	for(int i=1;i<n;i++)
	{
		if(a[i]==i)swap(a[i],a[i+1]),ans++;
	}
	if(a[n]==n)ans++;
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 640
n,m,c = map(int,input().split())
b = list(map(int,input().split()))
res = 0

for i in range(n):
    a = list(map(int,input().split()))
    tmp = c
    for i,j in zip(a,b):
        tmp += i * j
    if tmp > 0:
        res += 1

print(res)


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


int main() {
    string s,t;
    cin >> s >> t;
    reverse(s.begin(),s.end());
    if(s == t)cout << "YES\n";
    else cout << "NO\n";
    return 0;
}
/*
やっほい！
　　　　　　　やほほい！
　　　　+　　 　*
　　　 ∧∧　　. ∧∞∧　*
*　ヽ(=´ω｀)人(´ω｀*)ﾉ
　.～（ O x.） （ 　 O)～　+
。*　 　∪　　　　∪
*/

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

#define pb         push_back

typedef long long ll;
const ll INF = 1000000000000000000ll;
const ll MOD = 1000000007ll;
const double EPS = 1e-8;

ll dp[500][500];

long long gcd(long long a, long long b){
	while(a != b){
		if(a > b) a = a-b;
		else b = b - a;
	}
	return a;
}

int main(void) {
	//ios_base::sync_with_stdio(false);
	//cin.tie(0);
	
	int n, ma, mb;
	cin >> n >> ma >> mb;

	vector<int> a;
	vector<int> b;
	vector<int> c;
	a.pb(0);
	b.pb(0);
	c.pb(0);
	for(int i=0; i<n; i++){
		int ta, tb, tc;
		cin >> ta >> tb >> tc;
		a.pb(ta);
		b.pb(tb);
		c.pb(tc);
	}

	for(int j=0; j<=400; j++){
		for(int k=0; k<=400; k++){
			dp[j][k] = INF;
		}
	}

	dp[0][0] = 0;
	for(int i=1; i<=n; i++){
		for(int j=400; j>=0; j--){
			for(int k=400; k>=0; k--){
				if(j-a[i] >= 0 && k-b[i] >= 0){
					dp[j][k] = min(dp[j][k], dp[j-a[i]][k-b[i]] + c[i]);
				}else{
					dp[j][k] = dp[j][k];
				}
			}
		}

	}


	ll ans = INF;
	for(int j=1; j<=400; j++){
		for(int k=1; k<=400; k++){
			if(j/gcd(j, k) == ma && k/gcd(j,k) == mb){
				ans = min(ans, dp[j][k]);
			}
		}
	}
	if(ans == INF){
		puts("-1");
	}else{
		cout << ans << endl;
	}

	
	return 0;
}


Measured memory_bytes: 1792
import java.util.Scanner;

public class Main {
    private static final String HEISEI = "Heisei";
    private static final String TBD = "TBD";

    public static String process(TestCase testCase) {
        final String S = testCase.S;
        final StillTbdDate date = StillTbdDate.fromString(S);
        return date.asHeiSeiOrTbd();
    }

    private static class StillTbdDate {
        private final int year;
        private final int month;
        private final int day;

        private StillTbdDate(int year, int month, int day) {
            this.year = year;
            this.month = month;
            this.day = day;
        }

        public static StillTbdDate fromString(String S) {
            final String[] parts = S.split("/");
            int year = Integer.parseInt(parts[0]);
            int month = Integer.parseInt(parts[1]);
            int day = Integer.parseInt(parts[2]);

            return new StillTbdDate(year, month, day);
        }

        public String asHeiSeiOrTbd() {
            if (isTbd(year, month, day)) {
                return TBD;
            } else {
                return HEISEI;
            }
        }

        private boolean isTbd(int year, int month, int day) {
            final boolean isAfterYear = year > 2019;
            final boolean isAfterMonth = year == 2019 && month > 4;
            final boolean isAfterDay = year == 2019 && month == 4 && day > 30;
            return isAfterYear || isAfterMonth || isAfterDay;
        }
    }


    // Util func

    public static void main(String[] args) {
        TestCase testCase = readFromInput();

        final String result = process(testCase);

        output(result);
    }

    private static TestCase readFromInput() {
        Scanner sc = new Scanner(System.in);

        String S = sc.next();

        sc.close();
        return new TestCase(S);
    }

    private static void output(String result) {
        System.out.println(result);
    }

    public static class TestCase {
        final String S;

        public TestCase(String S) {
            this.S = S;
        }
    }
}


Measured memory_bytes: 21844
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char s[20];
int ans,a[20];
int main()
{
	scanf("%s",s);
	int n=strlen(s);
	for(int i=1;i<=n;i++)  a[i]=s[i-1]-'0';
	for(int i=1;i<=n;i++)
	{
		if(a[i]!=9)
		{
			ans-=1;
			ans+=(n-i+1)*9;
			break;
		}
		else ans+=9;
	}
	if(a[1]!=9)
	{
		ans=a[1]-1+(n-1)*9;
	}
	int sum=0;
	for(int i=1;i<=n;i++)  sum+=a[i];
	ans=max(ans,sum);
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod 1000000007
main()
{
     int n,i,p=0;
     cin>>n;
     for(i=1;i<=100;i++)
     {
         p+=1000;
         if(p>=n)break;
     }
     cout<<(p-n)<<endl;
}


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

using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;

#define fi first
#define se second

const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll MOD3 = 1812447359;
const ll INF = 1ll << 62;
const double PI = 2 * asin(1);

void yes() {printf("yes\n");}
void no() {printf("no\n");}
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

int N, Dist[int(1e5+5)];
vector <int> Graph[int(1e5+5)];
ll DP[int(1e5+5)][2];
bool checked[int(1e5+5)][2];

ll Solve(int num, int color){
  if (checked[num][color]) return DP[num][color];
  checked[num][color] = true;
  ll ans = 1;

  for (int next : Graph[num]){
    if (Dist[num] > Dist[next]) continue;
    if (color == 0){
      ans *= (Solve(next, 0) + Solve(next, 1)) % MOD;
    }else{
      ans *= Solve(next, 0);
    }
    ans %= MOD;
  }
  return DP[num][color] = ans;
}


int main(){
  cin >> N;
  fill(Dist, Dist + N + 1, -1);
  for (int i = 0; i < N - 1; i++){
    int X, Y; cin >> X >> Y;
    Graph[X].push_back(Y);
    Graph[Y].push_back(X);
  }
  queue <int> que; que.push(1);
  Dist[1] = 0;
  while (!que.empty()){
    int Q = que.front(); que.pop();
    for (int next : Graph[Q]){
      if (Dist[next] != -1) continue;
      que.push(next);
      Dist[next] = Dist[Q] + 1; 
    }
  }
  cout << (Solve(1, 0) + Solve(1, 1)) % MOD << endl;
  return 0;
}


Measured memory_bytes: 19480
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;

int read(){
    int x=0;bool f=0;char c=getchar();
    while(c<'0'||c>'9') f|=c=='-',c=getchar();
    while(c>='0'&&c<='9') x=x*10+(c^48),c=getchar();
    return f?-x:x;
}

#define MAXN 50000
#define MAXM 1000000
#define INF 1ll<<60
#define LL long long
struct Edge{
    LL w,c;
    int v,Next;
}E[MAXM+5];
int Adj[MAXN+5],ecnt;
void AddEdge(int u,int v,LL Cap,LL Cost){
    E[ecnt].v=v,E[ecnt].w=Cap,E[ecnt].c= Cost,E[ecnt].Next=Adj[u],Adj[u]=ecnt++;
    E[ecnt].v=u,E[ecnt].w=0,  E[ecnt].c=-Cost,E[ecnt].Next=Adj[v],Adj[v]=ecnt++;
}

int pre[MAXN+5];
LL Dist[MAXN+5];
bool vis[MAXN+5];
int cnt[MAXN+5];
bool SPFA(int S,int T,int N,LL &Flow,LL &Cost){
    for(int i=0;i<=N;i++)
        Dist[i]=INF,pre[i]=-1,vis[i]=0,cnt[i]=0;
    queue<int> Q;
    Q.push(S);
    Dist[S]=0,vis[S]=1;
    while(!Q.empty()){
        int u=Q.front();Q.pop();vis[u]=0;
        for(int i=Adj[u];i!=-1;i=E[i].Next){
            int v=E[i].v,c=E[i].c;
            if(E[i].w&&Dist[v]>Dist[u]+c){
                Dist[v]=Dist[u]+c;
                pre[v]=i;
                if(!vis[v]){
                    ++cnt[v];
                    vis[v]=1,Q.push(v);
                }
            }
        }
    }
    if(Dist[T]==INF)
        return 0;
    LL Min=INF;
    for(int i=pre[T];i!=-1;i=pre[E[i^1].v])
        Min=min(Min,(LL)E[i].w);
    for(int i=pre[T];i!=-1;i=pre[E[i^1].v])
        E[i].w-=Min,E[i^1].w+=Min,Cost+=Min*E[i].c;
    Flow+=Min;
    return 1;
}
pair<LL,LL> Dinic(int S,int T,int N){
    LL Flow=0,Cost=0;
    while(1)
        if(!SPFA(S,T,N,Flow,Cost))
            break;
    return make_pair(Flow,Cost);
}

#undef MAXN
#undef MAXM

#define MAXM 1000
int N,M,K;
int A[MAXM+5];

int main(){
    N=read();
    ecnt=0;
    memset(Adj,-1,sizeof Adj);
    for(int i=1;i<=N;i++){
        int x=read(),y=read(),c=read();
        AddEdge(1,i+1,c,0);
        AddEdge(i+1,N+2,INF,x+y);
        AddEdge(i+1,N+3,INF,-x+y);
        AddEdge(i+1,N+4,INF,x-y);
        AddEdge(i+1,N+5,INF,-x-y);
    }
    for(int i=1;i<=N;i++){
        int x=read(),y=read(),c=read();
        AddEdge(i+5+N,2*N+6,c,0);
        AddEdge(N+2,i+5+N,INF,-x-y);
        AddEdge(N+3,i+5+N,INF,x-y);
        AddEdge(N+4,i+5+N,INF,-x+y);
        AddEdge(N+5,i+5+N,INF,x+y);
    }
    printf("%lld",-Dinic(1,2*N+6,2*N+6).second);
    return 0;
}


Measured memory_bytes: 896
# -*- coding: utf-8 -*-

import sys
import os


X = int(input())

for t in range(1, 10**10):
    # t秒後にたどり着けるか
    # t秒経ったと言うことは、1 + 2 + ... + tだけ進めるということ
    S = t * (t + 1) / 2
    if S >= X:
        print(t)
        break


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

using namespace std;

#define REP(i, n)   for(int i = 0; i < (n); i++)
#define REPS(i, n)  for(int i = 1; i <= (n); i++)
#define RREP(i, n)  for(int i = (n)-1; i >= 0; i--)
#define RREPS(i, n) for(int i = (n); i > 0; i--)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
#define mp make_pair
#define mt make_tuple
#define pb push_back

using ll  = long long;
using pi  = pair<int, int>;
using pl  = pair<ll, ll>;
using vi  = vector<int>;
using vl  = vector<ll>;
using vs  = vector<string>;
using vb  = vector<bool>;
using vvi = vector<vi>;
using vvl = vector<vl>;

const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const ll  INFL = 1e18;
const double PI = 3.141592653589793;
const double EPS = 1e-9;

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

signed main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    string s; cin >> s;
    reverse(ALL(s));
    string w[] = {"maerd", "remaerd", "esare", "resare"};
    int i = 0;
    while(i < (int)s.length())
    {
        bool matched = false;
        REP(j, 4)
        {
            if(i < (int)s.length() && s.substr(i, (int)w[j].length()) == w[j]) i += (int)w[j].length(), matched = true;
        }
        if(!matched)
        {
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
}

Measured memory_bytes: 3768
#include <iostream>
#include <string> 
using namespace std;
 
int main() {
    string N;
    cin >> N;
    if (N[0] == N[1] && N[1] == N[2])
    cout << "Yes" << endl;
    else if ( N[1] == N[2] && N[2] == N[3] )
    cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 256
import java.util.*

//

fun main() {
    abc085d()
}

fun abc085d() {
    val (ns, hs) = readLine()!!.split(" ")
    val n = ns.toInt()
    var h = hs.toLong()
    val priorityQueue = PriorityQueue<Katana> {o1, o2 -> (o2.damage - o1.damage).toInt() }
    repeat(n) {
        val (a, b) = readLine()!!.split(" ").map { it.toLong() }
        priorityQueue.add(Katana(a, true))
        priorityQueue.add(Katana(b, false))
    }
    var count = 0L
    while (h > 0L) {
        val k = priorityQueue.poll()
        h -= k.damage
        count++
        if (k.repeat) {
            while (h > 0L) {
                h -= k.damage
                count++
            }
        }
    }
    println(count)
}

private data class Katana(val damage: Long, val repeat: Boolean)

Measured memory_bytes: 65820
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;cin>>n;double p[n+1];for(int i=1;i<n+1;i++)cin>>p[i];
    double dp[n+1][n+1]={0};dp[0][0]=1.0;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=i;j++)
        {
            if(j==0)dp[i][j]=dp[i-1][j]*(1-p[i]);
            else
            dp[i][j]=dp[i-1][j-1]*p[i]+dp[i-1][j]*(1-p[i]);
        }
    }double ans=0;
 //  for(int i=1;i<=n;i++)
 // { for(int j=1;j<=n;j++)cout<<dp[i][j]<<' ';cout<<endl;}
 for(int i=1;i<=n;i++)
 {
     if(n-i<i)
     ans+=dp[n][i];
 }
    cout<<fixed<<setprecision(20)<<ans;
}

Measured memory_bytes: 70528
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a[55];
    int mx=-1e9,mn=1e9;
    int x,nn;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        if(mx<a[i])
        {
            mx=a[i];
            x=i;
        }
        if(mn>a[i])
        {
            mn=a[i];
            nn=i;
        }
    }
    if(mx>0&&mn>0)
    {
        cout<<n-1<<endl;
        for(int i=0;i<n-1;i++)
            cout<<i+1<<' '<<i+2<<endl;
    }
    else if(mx<0&&mn<0)
    {
        cout<<n-1<<endl;
        for(int i=n-2;i>=0;i--)
            cout<<i+2<<' '<<i+1<<endl;
    }
    else if(abs(mn)>mx)
    {
        cout<<2*n-1<<endl;
        for(int i=0;i<n;i++)
            cout<<nn+1<<' '<<i+1<<endl;
        for(int i=n-2;i>=0;i--)
            cout<<i+2<<' '<<i+1<<endl;
    }
    else
    {
        cout<<2*n-1<<endl;
        for(int i=0;i<n;i++)
            cout<<x+1<<' '<<i+1<<endl;
        for(int i=0;i<n-1;i++)
            cout<<i+1<<' '<<i+2<<endl;
    }

}


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

int main(){
    string S;
    cin >> S;
    if ((S[0] == S[1] && S[1] == S[2]) or (S[1] == S[2] && S[2] == S[3])){
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;
using ll = long long;

#define all(c) (c).begin(), (c).end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define pb(e) push_back(e)
#define mp(a, b) make_pair(a, b)
#define fr first
#define sc second

const ll INF = 1e9;
const ll MOD = 1e9 + 7;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int x, y, s;
int f(int i, int j, int z) { return i * (100 + z) / 100 + j * (100 + z) / 100; }
void solve() {
    int ans = 0;
    rep(i, s + 1) rep(j, s + 1) if (i && j && f(i, j, x) == s) {
        // cout << i << ", " << j << ": " << f(i,j,y) << endl;
        ans = max(ans, f(i, j, y));
    }
    cout << ans << endl;
}
int main() {
    while (cin >> x >> y >> s, x) {
        solve();
    }
    return 0;
}

Measured memory_bytes: 3076
import scala.io.StdIn._
import scala.collection.mutable._
object Main{
  def main(args:Array[String]) {
    val N = readLine().toInt
    val m = Map("AC"->0, "WA"->0, "TLE"->0, "RE"->0)
    for(i <- 0 until N) {
      m(readLine()) += 1
    }
    println("AC x " + m("AC"))
    println("WA x " + m("WA"))
    println("TLE x " + m("TLE"))
    println("RE x " + m("RE"))
  }
}


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

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

#define ll long long
#define pi pair<int, int>
#define pll pair<ll, ll>

#define MOD 1000000007
#define INF 1000000000000000LL

using namespace std;

#define MAX_N 200000
vector<ll>g[MAX_N];

vector<int> group[2];
void dfs(ll pre, ll now, ll d){
  group[d].push_back(now);
  for(auto to: g[now]){
    if(pre!=to) dfs(now, to, d^1);
  }
}

int main(){
  ll n;cin>>n;
  rep(i, n-1){
    ll a,b;cin>>a>>b;
    a--;b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }

  dfs(-1, 0, 0);

  vector<int> num[3];
  rep1(i, n)num[i%3].push_back(i);

  vector<int> result(n);

  if(group[0].size() <= n/3){
    for(auto tmp: group[0]){
      result[tmp] = num[0].back();
      num[0].pop_back();
    }
    for(auto tmp: group[1]){
      rep(i, 3){
        if(num[i].empty())continue;
        result[tmp] = num[i].back();
        num[i].pop_back();
        break;
      }
    }
    rep(i, n)cout<<result[i]<<' ';
    return 0;
  }

  swap(group[0], group[1]);

  if(group[0].size() <= n/3){
    for(auto tmp: group[0]){
      result[tmp] = num[0].back();
      num[0].pop_back();
    }
    for(auto tmp: group[1]){
      rep(i, 3){
        if(num[i].empty())continue;
        result[tmp] = num[i].back();
        num[i].pop_back();
        break;
      }
    }
    rep(i, n)cout<<result[i]<<' ';
    return 0;
  }

  rep(i, 2){
    for(auto tmp:group[i]){
      if( !num[i+1].empty() ){
        result[tmp] = num[i+1].back();
        num[i+1].pop_back();
      }else{
        result[tmp] = num[0].back();
        num[0].pop_back();
      }
    }
  }
  rep(i, n)cout<<result[i]<<' ';

  return 0;
}

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

int main() {
    ll N;
    cin >> N;
    vector<ll> A(N);

    for (ll i=0; i<N; i++){
        cin >> A.at(i);
    }

    ll sum = 0;
    ll temp = 0;

    for (ll i=0; i<N-1; i++){
        if (A.at(i) < A.at(i+1)){
            temp = 0;
        }
        else {
            temp = A.at(i) - A.at(i+1);
            A.at(i+1) = A.at(i);
        }
        sum += temp;
    }

    cout << sum << endl;


}


Measured memory_bytes: 4828
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

static class Program
{
    static double Solve(int N, int K, int[] P)
    {
        var S = new double[1001];
        for (int i = 1; i <= 1000; ++i) { S[i] = S[i - 1] + i; }

        int maxi = 0;
        long sum = P.Take(K).Sum();
        long max = sum;
        for (int i = 1; i + K - 1 < N; ++i)
        {
            sum += P[i + K - 1];
            sum -= P[i - 1];
            if (sum > max)
            {
                maxi = i;
                max = sum;
            }
        }
        double ans = 0;
        for (int i = 0; i < K; ++i)
        {
            int j = maxi + i;
            ans += S[P[j]] / P[j];
        }
        return ans;
    }

    static void Main(string[] args)
    {
        int[] V = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
        int[] P = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
        Console.WriteLine(Solve(V[0], V[1], P));
    }
}


Measured memory_bytes: 29532
#include <stdio.h>
int main(){
int i,n,l=0,p[100];
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d ",&p[i]);
}
for(int i=1;i<n-1;i++){
if((p[i-1]<p[i]&&p[i]<p[i+1])||(p[i-1]>p[i]&&p[i]>p[i+1]))
l++;
}
printf("%d ",l);
}

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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,M,L = 0,R = INT_MAX,x;
    cin >> N >> M;
    REP(i,M){
        cin >> x;
        L= max(L,x);
        cin >> x;
        R= min(R,x);
    }
    if(R-L+1>=0){
    cout <<R-L+1<< "\n";
    }else{
    cout <<0<< "\n";
    }
}

Measured memory_bytes: 256
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main(){
	int t,a,b,c,sum;
      cin>>a>>b>>c;
      sum=max<int>({
	  10*a+b+c,
	  a+10*b+c,
	  a+b+10*c,
	  });
	cout<<sum<<"\n";
	
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define vi vector<int>
#define vvi vector<vector<int> >
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vc vector<char>
#define vs vector<string>
using ll = long long;
using ld =long double;
//#define int ll
#define INF 1e9
#define EPS 0.0000000001
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define all(in) in.begin(), in.end()
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
#define MAX 9999999
using namespace std;
typedef pair<int, int> pii;
typedef pair<int,pii> piii;
#define mp make_pair
signed main(){
    int n;cin>>n;
    cout<<n/3<<endl;
}


Measured memory_bytes: 256
//#define LOCAL

#include <fstream>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <cstring>
#include <climits>
#include <set>

//#define int long long
typedef long long ll;
//using ll = long long;
//using R = double;

//#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,bg,ed) for(ll i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)

#define MOD 1000000007

const int INF = int(1e9);

using namespace std;

typedef vector<int> V;
typedef vector<V> VV;

string s, ss;

bool same(string s)
{
    if (s.length() == 1) return true;
    REP(i,s.length()) {
        if (s[i] != s[0]) return false;
    }
    return true;
}

string func(string s, char c)
{
    int len = s.length();
    REP(i,len-1) {
        s[i] = (s[i+1] == c ? s[i+1] : s[i]);
    }
    s.resize(len - 1);
    return s;
}

signed main()
{
    cin >> s;

    int ans = 10000;
    for (char c='a'; c<='z'; c++) {
        ss = s;
        int cnt = 0;
        while (!same(ss)) {
            cnt++;
            ss = func(ss, c);
        }
        ans = min(ans, cnt);
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
N = int(input())
L = [tuple(map(int, input().split())) for _ in range(N)]

xx, yy, hh = next(l for l in L if l[2] >= 1)
for Cx in range(101):
    for Cy in range(101):
        H = hh + abs(xx - Cx) + abs(yy - Cy)
        for x, y, h in L:
            if h != max(H - abs(x - Cx) - abs(y - Cy), 0):
                break
        else:
            print(Cx, Cy, H)
            quit()

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define N 100
using namespace std;
bool used[N][N];
string d[N];
int h,w,ans;
char c;
int dy[4]={-1,0,1,0};
int dx[4]={0,1,0,-1};

void dfs(int y,int x){
  used[y][x]=true;
  for(int i=0;i<4;i++){
    int ny=y+dy[i],nx=x+dx[i];
    if(ny<0||nx<0||h<=ny||w<=nx)continue;
    if(used[ny][nx]||d[ny][nx]!=c)continue;
    dfs(ny,nx);
  }
}

int main(){
  while(1){
    cin>>h>>w;
    if(!h&&!w)break;
    for(int i=0;i<h;i++)cin>>d[i];
    ans=0;
    memset(used,0,sizeof(used));
    for(int i=0;i<h;i++)
      for(int j=0;j<w;j++)
	if(!used[i][j])c=d[i][j],dfs(i,j),ans++;
    cout<<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 2020
#include<bits/stdc++.h>
#define l(x) (x<<1)
#define r(x) (x<<1)|1
#define pb push_back
const int N = 500000 + 10;
using namespace std;

int n,m,e;
int mx[N<<2],t[N],s[N],b[N],bgn[N<<1],to[N<<2],nxt[N<<2];
int v[N],snt;

priority_queue<int, vector<int>, greater<int> > q;
namespace seg
{
  inline int ckmx(int a,int b)
  {
    return a>b?a:b;
  }
  void mt(int x){mx[x]=ckmx(mx[l(x)],mx[r(x)]);}
  void upd(int x,int l,int r,int p,int v)
  {
    if(l==r) {mx[x]=v; return;} 
	int m=(l+r)>>1;
	if(p<=m) upd(l(x),l,m,p,v); else upd(r(x),m+1,r,p,v);
	mt(x);
  }
  int qury(int x,int l,int r,int ql,int qr)
  {
    if(ql<=l&&r<=qr) return mx[x]; 
	else
	{
	  int g=0,m=(l+r)>>1;
	  if(ql<=m) g=ckmx(g,qury(l(x),l,m,ql,qr));
	   if(m<qr) g=ckmx(g,qury(r(x),m+1,r,ql,qr));
	  return g;
	}
  }
}

using namespace seg;

namespace solver
{
  int abs(int x) { return x > 0 ? x : -x;}
  void add(int x,int y)
  {
    to[++e]=y; nxt[e]=bgn[x]; bgn[x]=e;
  }
  void dfs(int x=0)
  {
    int sz=0;
	s[snt++]=x;
    for(int i=bgn[x]; i; i=nxt[i]) q.push(to[i]);
	while(!q.empty())
	{
	  int y=q.top(); q.pop();  dfs(y);
	}
   }
  void solve()
  {
    scanf("%d%d",&n,&m);
    int x(0);
	for(int i=1; i<=n; ++i)
	{
	  scanf("%d",&x);
	  b[i]=x;t[x]=i;
	}	
	for(int i=1; i<=n; ++i)
	{
	  int ps=qury(1,1,n,t[i]+1,t[i]+m-1);
      upd(1,1,n,t[i],i);
	  add(t[ps],t[i]);
	}
	dfs();
	for(int i=1; i<=n; ++i) b[s[i]]=i;
	for(int i=1; i<=n; ++i) printf("%d\n",b[i]);
  }    
}

int main()
{
  solver :: solve();
}

Measured memory_bytes: 35060
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <math.h>
#include<bitset>
#include<stdio.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)

bool isOK(int a[],int index,int key){
    if(a[index] >= key){
        return true;
    }else{
        return false;
    }
}

int binary_search(int a[],int n,int key){
    int left = -1;
    int right = n;

    while(right-left>1){
        int mid = left + (right - left)/2;
        if(isOK(a,mid,key)){
            right = mid;
        }else{
            left = mid;
        }
    }
    return right;
}



int main(void){
    int n,m;
    cin >> n >> m;

    if(n==m){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+50,mo=1e9+7;
inline int gi() {
  char ch=getchar(); int q=0,x=0;
  while(ch<'0'||ch>'9') q=(ch=='-'?1:q),ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
  return q?(-x):x;
}
int a[N],b[N],v[N],f[N],tot;
struct data{
  int x,y;
  bool operator < (const data &c)const{
    return x==c.x?y>c.y:x<c.x;
  }
}w[N];
void add(int x,int s){
  while(x<=tot) (f[x]+=s)%=mo,x+=x&-x;
  return;
}
int qry(int x){
  int s=1;
  while(x) (s+=f[x])%=mo,x-=x&-x;
  return s;
}
int main(){
  int n=gi(),m=gi();
  for (int i=1; i<=n; ++i) a[i]=gi();
  for (int i=1; i<=m; ++i) b[i]=gi();
  for (int i=1,j=1; i<=n; ++i){
    while(j<m&&a[i]>b[j]) ++j;
    if (j>1&&a[i]<b[j]) w[++tot]=(data){a[i]-b[j-1],b[j]-a[i]};
  }
  sort(w+1,w+tot+1);
  for (int i=1; i<=tot; ++i)
    v[i]=w[i].y;
  sort(v+1,v+tot+1);
  for (int i=1; i<=tot; ++i){
    if (w[i].x==w[i-1].x&&w[i].y==w[i-1].y) continue;
    int t=lower_bound(v+1,v+tot+1,w[i].y)-v;
    add(t,qry(t-1));
  }
  cout<<qry(tot);
  return 0;
}

Measured memory_bytes: 2560
#include <iostream>
#include <string>
#include <stack>
#include <cstdlib>
using namespace std;
int main() {
    string word;
    stack<int> S;
    while(cin >> word)
    {
        if(word == "+")
        {
            int x = S.top();
            S.pop();
            int y = S.top();
            S.pop();
            S.push(x+y);
        }
        else if(word == "-")
        {
            int x = S.top();
            S.pop();
            int y = S.top();
            S.pop();
            S.push(y-x);
        }
        else if(word == "*")
        {
            int x = S.top();
            S.pop();
            int y = S.top();
            S.pop();
            S.push(x*y);
        }
        else
        {
            S.push(atoi(word.c_str()));
        }
    }
    int s = S.top();
    cout<<s<<endl;
    return 0;
}

Measured memory_bytes: 3164
using System;
using System.Threading;

namespace contest
{
    class Program
    {
        static void Main(string[] args)
        {
            char[] s = Console.ReadLine().ToCharArray();
            char[] t = Console.ReadLine().ToCharArray();
            int count = 0;
            for (int i = 0; i < s.Length; i++)
            {
                if (s[i] != t[i])
                {
                    count++;
                }
            }
            {

            }
            Console.WriteLine(count);
        }
    }
}


Measured memory_bytes: 28216
#include<iostream>
using namespace std;
int main()
{
    int n;
    cin >> n;
    float a[n];
    float sum = 0;
    for (int i = 0;i<n;i++){
        cin >> a[i];
        //sum = sum + 1/a[i];
    }
    for (int i = 0;i<n;i++){
        //cout << a[i] << " ";
        sum = sum + 1/a[i];
    }
    cout << (1/sum);
}

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

using namespace std;

int main() {
	int N, A, B, a, b;
	string s;
	cin >> N >> A >> B;
	cin >> s;
	a = b = 0;
	for(int i=0;i<s.length();i++) {
		switch(s[i]) {
			case 'a':
				if(a + b < A + B) {
					puts("Yes");
					a++;
				} else puts("No");
				break;
			case 'b':
				if(a + b < A + B && b < B) {
					puts("Yes");
					b++;
				} else puts("No");
				break;
			case 'c':
				puts("No");
				break;
			default:
				break;
		}
	}

	return 0;
}


Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)
#define pai 3.14159265358979323846
const int INF = 1001001001;
typedef long long ll;
int A[3][3], N;
bool punched[3][3];
bool ok[3][3];
int a[3][3],n;
using Graph = vector<vector<int>>;
vector<vector<int>> field;
vector<bool> seen;

const int MOD = 1000000007;
int main() {
 int n;
 cin >> n;
 int w[n];
 int sum1=0,sum2=0;
 rep (i,n) {
   cin >> w[i];
   sum1+=w[i];
 }
 int mini = INF;
 rep (i,n){
   sum1-=w[i];
   sum2+=w[i];
   mini = min(mini,abs(sum1-sum2));

 }
 cout << mini << endl;


}


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

void solve()
{
    int n;
    scanf("%d", &n);
    vector<int> a(n),b(n),sa(n+1),sb(n+1);
    int i;
    for(i=0; i<n; i++) {
        scanf("%d", &a[i]);
    }
    for(i=0; i<n; i++) {
        scanf("%d", &b[i]);
    }
    for(i=0; i<n; i++) {
        sa[i+1]=sa[i]+a[i];
    }
    for(i=n-1; i>=0; i--) {
        sb[i]=sb[i+1]+b[i];
    }
    ll ans=-LINF;
    for(i=0; i<n; i++) {
        ll tmp=sa[i+1]+sb[i];
        ans=MAX(ans,tmp);
    }
    printf("%lld\n", ans);

    return;
}

int main(int argc, char* argv[])
{
#if 1
    solve();
#else
    int T; scanf("%d", &T);
    while(T--) {
        solve();
    }
#endif
    return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Main {
	private	static	BufferedReader	br = null;

	static {
		br   = new BufferedReader(new InputStreamReader(System.in));
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String	strTmp   = null;
		String	strStdin = null;
		char[]	aStdin   = null;
		char	c;

		while((strStdin = parseStdin()) != null) {
			aStdin = strStdin.toCharArray();
			for (int n1 = 0; n1 < 26; n1++) {
				for (int n2 = 0; n2 < aStdin.length; n2++) {
					c = aStdin[n2];
					if ('a' <= c && c <= 'z') {
						if ('z' < ++c) {
							c = 'a';
						}
					}
					aStdin[n2] = c;
				}
				strTmp = String.valueOf(aStdin);
				if (strTmp.contains("this") || strTmp.contains("that") || strTmp.contains("the")) {
					System.out.println(strTmp);
					break;
				}
			}
		}
	}

	private static String parseStdin() {
		String	strNum = null;

		try {
			String line = br.readLine();
			if (line != null) {
				if (!line.isEmpty()) {
					strNum = line;
				}
			}
		}
		catch (IOException e) {}

		return strNum;
	}
}

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

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    vector<int>dp(3);
    for(int day=0; day<n; ++day) {
        vector<int> new_dp(3, 0);
        vector<int> c(3);   
        cin >> c[0] >> c[1] >> c[2];
        for(int i=0; i<3; ++i) {
            for(int j=0; j<3; ++j) {
                if(i!=j) {
                    new_dp[j] = max(new_dp[j], dp[i]+c[j]);
                }
            }
        }
        dp = new_dp;
    }
    cout << max(dp[0],max(dp[1],dp[2])) << "\n";
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0; i<(int)(n); ++i)
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using Graph = vector<vi>;  // vi <=> vl
using P = pair<int, int>;  // int <=> ll
const int MOD = 1e9+7;
const double EPS = 1e-9;

void solve() {
  Graph G(3, vi(3));
  rep(i,3) rep(j,3) cin >> G[i][j];

  rep(i,2) {
    rep(j,2) {
      if (G[0][0] - G[0][j+1] != G[i+1][0] - G[i+1][j+1]) {
        cout << "No\n";
        return;
      }
    }
  }
  cout << "Yes\n";
  return;
}

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


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

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

  if (a >= 3200)
    cout << s << endl;
  else
    cout << "red" << endl;
  return 0;
}

Measured memory_bytes: 3548
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;

int def[110];
// dp[i][j][k] ???i??\??????j,i-1??\??????k????????¶??????????????????????????????
int dp[110][4][4];

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

	int n, k;
	cin >> n >> k;

	for(int i = 0; i < k; ++i){
		int a, b;
		cin >> a >> b;
		def[a - 1] = b;
	}

	if(def[0] != 0){
		dp[0][def[0]][0] = 1;
	}
	else {
		for(int j = 1; j <= 3; ++j){
			dp[0][j][0] = 1;
		}
	}

	for(int i = 1; i < n; ++i){
		if(def[i] != 0){
			for(int k = 1; k <= 3; ++k){
				for(int l = 0; l <= 3; ++l){
					if(def[i] != k || def[i] != l){
						dp[i][def[i]][k] += dp[i - 1][k][l];
						dp[i][def[i]][k] %= 10000;
					}
				}
			}
		}
		else {
			for(int j = 1; j <= 3; ++j){
				for(int k = 1; k <= 3; ++k){
					for(int l = 0; l <= 3; ++l){
						if(j != k || j != l){
							dp[i][j][k] += dp[i - 1][k][l];
							dp[i][j][k] %= 10000;
						}
					}
				}
			}
		}
	}
	
	//for(int i = 0; i < n; ++i){
		int sum = 0;
		for(int j = 1; j <= 3; ++j){
			for(int k = 1; k <= 3; ++k){
				sum += dp[n - 1][j][k];
				sum %= 10000;
			}
		}
		cout << sum << endl;
	//}

	return 0;
}

Measured memory_bytes: 3136
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
using ll = long long;

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

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

    int r = 0;
    for (int i = a; i <= b; i++) {
        if (i % k == 0) r = 1;
    }

    cout << (r ? "OK" : "NG") << endl;

    return 0;
}

Measured memory_bytes: 3620
N = int(input())
a = list(map(int,(input().split())))
from collections import Counter
c = Counter(a)
L = []
LL = []
for k in c.keys():
    if c[k] >= 2:
        L.append(k)
    if c[k] >= 4:
        LL.append(k)
M = 0 
if LL:
    M = max(LL)**2
if len(L) < 2:
    print(0)
else:
    L.sort(reverse=True)
    print(max(L[0]*L[1],M))

Measured memory_bytes: 68760
N, K = map(int, input().split())
x = list(map(int, input().split()))
ress = [] 
for i in range(N-K+1):
    l = i
    r = i+K-1
    ress.append(abs(x[l]) + abs(x[r]-x[l]))
    ress.append(abs(x[r]) + abs(x[r]-x[l]))

print(min(ress))

Measured memory_bytes: 14224
#include <iostream>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <tuple>
#include <algorithm>
#include <functional>
#include <cstring>
#include <limits.h>
#define FOR(i,k,n)  for (int i=(k); i<(int)(n); ++i)
#define REP(i,n)    FOR(i,0,n)
#define FORIT(i,c)	for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define SZ(i) ((int)i.size())
#define pb          push_back
#define mp          make_pair
#define mt          make_tuple
#define get0(x)     (get<0>(x))
#define get1(x)     (get<1>(x))
#define get2(x)     (get<2>(x))
#define ALL(X)      (X).begin(),(X).end()
#define LLMAX       9223372036854775807LL
#define LLMIN       -9223372036854775808LL
#define IMAX        2147483647
#define IMIN        -2147483648
typedef long long LL;
using namespace std;

int main(void){
    string s;
    cin>>s;
    cout<<s.substr(0,SZ(s)-8)<<endl;
     return 0;
}

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

int main(void)
{
    string S;
    cin >> S;

    int favorite = 753;
    int min = 753;
    int first = 0, second = 0, third = 0, num = 0;
    for (int i = 0; i < S.size() - 2; i++)
    {
        first = (S[i] - '0') * 100;
        second = (S[i + 1] - '0') * 10;
        third = S[i + 2] - '0';
        num = first + second + third;
        // cout << num << endl;

        if (min > abs(favorite - num))
        {
            min = abs(favorite - num);
            // cout << num << endl;
        }
    }
    cout << min << endl;
    return (0);
}

Measured memory_bytes: 256
#include <iostream>
#include <assert.h>
#include <vector>
#include <unordered_map>
#include <queue>
#include <climits>
#include <cmath>
#include <algorithm>
using namespace std;
constexpr int64_t MOD = 1e9 + 7;

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

  string S;
  cin >> S;
  int size = (int)S.size();
  if (size % 2 == 1) {
    cout << "No" << endl;
    return 0;
  } else {
    for (int i = 0; i < size; i+=2) {
      if (S[i] != 'h' || S[i+1] != 'i') {
        cout << "No" << endl;
        return 0;
      }
    }
  }
  cout << "Yes" << endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<deque>
using namespace std;
#define ll long long
const int mod = 1000000007;
const int MOD = 998244353;
const ll INF = 1000000000000000000;


int main()
{
	int N, K;
	cin >> N >> K;
	if (K == 1) cout << 0 << endl;
	else cout << N - K << endl;
}

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

#define pb push_back

#define int ll
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vpii = vector<pii>;
using vvpii = vector<vpii>;

template<typename T, typename U>
ostream& operator<<(ostream& o, const pair<T,U>& p) {
  return o << "(" << p.first << "," << p.second << ")";
}

template<typename T>
ostream& operator<<(ostream& o, const vector<T>& v) {
  o << "[";
  for (const T& x : v)
    o << x << ",";
  return o << "]";
}

template<typename T>
ostream& operator<<(ostream& o, const vector<vector<T>>& v) {
  o << "[";
  for (const vector<T>& x : v)
    o << x << ",\n";
  return o << "]";
}

const int INF = 2e18;

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;
  vi as(n+1);
  for (int& ai : as)
    cin >> ai;

  bool possible = true;
  // compute upper bound
  vi bs(n+1);
  int r = 1;
  for (int i=0; i<=n; ++i) {
    r -= as[i];
    if (r < 0) {
      possible = false;
      break;
    }
    bs[i] = r;
    r *= 2;
    r = min(r, INF);
  }
  if (!possible) {
    cout << "-1\n";
    return 0;
  }

  vi inner(n+1);
  inner[n] = 0;
  for (int i=n-1; i>=0; --i) {
    int xl = as[i+1] + inner[i+1];
    if ((xl+1)/2 > bs[i]) {
      possible = false;
      break;
    }
    inner[i] = min(xl, bs[i]);
  }
  if (!possible) {
    cout << "-1\n";
    return 0;
  }

  int sum = 0;
  for (int lc : as)
    sum += lc;
  for (int ic : inner)
    sum += ic;
  cout << sum << endl;
}


Measured memory_bytes: 5560
n = int(input())
coords = [tuple(map(int, input().split())) for i in range(n)]
for xt, yt, ht in coords:
    if ht != 0:
        break
x, y, h = -1, -1, -1
for px in range(101):
    for py in range(101):
        flag = True
        htmp = ht + abs(px-xt) + abs(py-yt)
        dxdy = [(abs(px-x1)+abs(py-y1), htmp-h1) for x1, y1, h1 in coords]
        dxdy.sort()
        for i in range(n-1):
            if dxdy[i][0] < dxdy[i+1][0] and dxdy[i][1] > dxdy[i+1][1]:
                flag = False
                break
        for x1, y1, h1 in coords:
            #print (px, py, htmp, x1, y1, h1)
            if h1 == 0:
                continue
            if abs(htmp-h1) != abs(px-x1) + abs(py-y1):
                flag = False
                break
        if flag:
            if htmp > h:
                h = htmp
                x = px
                y = py
print (x, y, h)

Measured memory_bytes: 9132