akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>

int main(void)
{
    int n, x;
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
    {
        x = i;
        if(x%3==0) printf(" %d", i);
        else
        {
            while(1)
            {
                if(x%10==3)
                {
                    printf(" %d", i);
                    break;
                }
                x /= 10;
                if(x!=0) continue;
                break;
            }
        }
    }
    printf("\n");

    return 0;
}


Measured memory_bytes: 2764
package main

import "fmt"

func main() {
    var a int
    var b int
 //   var ans="No" 

    fmt.Scan(&a, &b)

   // ans := ""
    if (a*b%2 ==0) {
        fmt.Println("Even")
    } else {
        fmt.Println("Odd")
    }

    
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
 
#define int long long
#define ll long long 
#define f(i,l,n) for(int i=l;i<n;i++)
#define E "\n"
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define MAX 1e18
#define float long double
 
const int N=4006;
int n;
string s;

int R[N+1],G[N+1],B[N+1];
int cnt(int i,int j)
{
	int dif=j-i;

	if(s[i]==s[j]) return 0;

	char baki='R'+'G'+'B'-s[i]-s[j];

	int ans=0;
	if(baki=='R') ans=R[n+1]-R[j];
	else if(baki=='G') ans=G[n+1]-G[j];
	else  ans=B[n+1]-B[j];

	if(j+dif<=n and s[j+dif]==baki) ans--;
	return ans;


}

int32_t main()
{
 

  cin >> n >> s;
  s='a'+s;
  
  s=s+'a';
  f(i,1,n+2)
  {
  	R[i]=(s[i]=='R')+R[i-1];
  	G[i]=(s[i]=='G')+G[i-1];
  	B[i]=(s[i]=='B')+B[i-1];
  }


  int ans=0;
  f(i,1,n+1)
  {
  		for(int j=i+1;j<=n;j++)
  		{
  			ans+=cnt(i,j);
  		}
  }
  cout<<ans<<E;
  


}

Measured memory_bytes: 3736
/*
 * Lang  : C++ 17
 * Author: little_angel
 * Date  : 04-07-2020 10:40 04
 */

#include<bits/stdc++.h>

using namespace std;
#define int long long

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

    int h, w, k;
    cin >> h >> w >> k;
    vector<string> s(h);
    int tot = 0;
    for (int i = 0; i < h; ++i) {
        cin >> s[i];
        for (int j = 0; j < w; ++j) {
            if (s[i][j] == '#')tot++;
        }
    }
    int ans = 0;
    for (int r = 0; r < (1ll << h); ++r) {
        for (int c = 0; c < (1ll << w); ++c) {
            int cur = tot;
            for (int i = 0; i < h; ++i) {
                for (int j = 0; j < w; ++j) {
                    if ((((1ll << i) & r) or ((1ll << j) & c)) and s[i][j] == '#')cur--;
                }
            }
            if (cur == k)ans++;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3608
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	long long int a[n];
	
	for(int i=0;i<n;i++){
		cin >> a[i];
	}

	sort(a,a+n);
	long long int l=a[n-1],r=-1000;
	
	long long int mid;
	mid = l%2==0? l/2 : (l+1)/2;
	for(int i=0;i<n-1;i++){
		if(abs(a[i] - mid) < abs(mid-r)) r = a[i];
	}
	
	cout << l <<" " << r << "\n";
	return 0;
}

Measured memory_bytes: 1024
from collections import deque
H,W,K=map(int,input().split())
A=[list(input())for _ in range(H)]
for i,a in enumerate(A):
	if"S"in a:y,x=(i,a.index("S"))
d=1e9
Q=deque([(0,y,x)])
while Q:
	c,i,j=Q.popleft()
	d=min(d,i,j,H-i-1,W-j-1)
	if c>=K:continue
	for h,w in((i+1,j),(i,j+1),(i-1,j),(i,j-1)):
		if 0<=h<H and 0<=w<W and A[h][w]==".":
			A[h][w]=""
			Q+=[(c+1,h,w)]
print(1-(-d//K))

Measured memory_bytes: 75356
#include<stdio.h>
int main(){
  int ans;
  long long int X,Y,a;
  scanf("%lld %lld",&X,&Y);
  
  a=X;
  ans=0;
  while(Y>=a){
    a=2*a;
    ans++;
  }
  
  printf("%d",ans);
  return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
int const maxn=1e6+5;
int p[maxn];
int main(){
	int N;
	scanf("%d",&N);
	int num=0;
	for(int i=1;i<N;i++){
		for(int j=1;j<=i;j++){
			if(i*j<N){
				if(i==j) num++;
				else num+=2;
			}
			else break;
		}
	}
	printf("%d\n",num);	
	return 0;
}

Measured memory_bytes: 3824
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main(void){
    int n;
    cin >> n;
    int a = n%10;
    if(a==3) cout << "bon" << endl;
    else if(a==0||a==1||a==6||a==8) cout << "pon" << endl;
    else cout << "hon" << endl;
}


Measured memory_bytes: 3628
#include<iostream>
#include<string>
#include<map>
using namespace std;
int main(){
  int n,ss,max=0;
  cin >> n;
  string s;
  map<string,int> m;
  map<string,int>::iterator p;
  for(int i=0;i<n;i++){
    cin >> s >> ss;
    m[s] += ss;
    if(s.size()>max) max = s.size();
  }
  for(int i=1;i<=max;i++){
    for(p=m.begin();p!=m.end();p++){
      if(p->first.size()==i) cout << p->first << ' ' << p->second << endl; 
    }
  }
  return 0;
}

Measured memory_bytes: 1224
#include <bits/stdc++.h>
using namespace std;
vector<int>a;
int dp[1000000];
int n;

int recur(int i){
    if(dp[i] != -1){
        return dp[i];
    }else if(i == n-1){
      return 0;
    }
    dp[i] = (abs(a[i] - a[i+1]) + recur(i+1));
    if(i+2 <= n-1){
        dp[i] = min(dp[i], (abs(a[i] - a[i+2]) + recur(i+2)));
    }
    return dp[i];
}

int main(){
    cin>>n;
    for(int i = 0; i < n; i++){
        int b;
        cin>>b;
        a.push_back(b);
    }
    memset(dp,-1,sizeof dp);
    cout<<recur(0);
}


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

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    //[]でなく()でメモリ確保
    rep(i,n) cin >> a[i];
    rep(i,n) a[i]--;
    //なぜか0始まりがいいらしい。
    vector<int> idx(n);
    //iがどの場所にあるかを、
    //つまりindexをすぐに得るためのvec
    rep(i,n) idx[a[i]] = i;
    //このためにa[i]--したのかな？
    set<int> s;
    ll ans=0;
    for(int x= n-1;x>=0;x--){
        //大きい順に.
        //今回、問題設定より、最大値はn,
        //全て異なる値ってのが決まっている。
        int i = idx[x];
        //お手軽index取得.こういう問題設定の時しか無理そうだけど。
        ll c = 0;
        { // calc c
            s.insert(i);
            vector<int> l(2,-1);
            vector<int> r(2,n);
            //チェックしたものをここに保存.
            {//calc l
              auto it = s.find(i);
              rep(j,2){
                if(it == s.begin())break;
                --it;
                l[j]=*it;
              }
            //setのiterator
            }
            {//calc r
              auto it = s.find(i);
              rep(j,2){
                  ++it;
                  if(it == s.end())break;
                  r[j] = *it;
              }
            }
            vector<int> ls(2);
            ls[0] = i-l[0]; ls[1] = l[0] - l[1];
            vector<int> rs(2);
            rs[0] = r[0]-i; rs[1] = r[1] - r[0];
            c = (ll)ls[0]*rs[1] + (ll)ls[1]*rs[0];
        }
        ans += c*(x+1);
        //先に答えを書いてしまう.
    }
    cout<<ans<<endl;
    return 0;
}

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

namespace ConsoleTest
{
    static partial class Program
    {
        static long Calc(long n, long k)
        {
            if (n <= k)
            {
                return Math.Min(n, k - n);
            }
            return Calc(n % k, k);
        }
        static void Main(string[] args)
        {
            var v = Longs();
            long n = v[0];
            long k = v[1];

            Console.WriteLine(Calc(n, k));
        }
    }
    static partial class Program
    {
        public static int Int()
        {
            return int.Parse(Console.ReadLine());
        }
        public static int[] Ints()
        {
            return Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
        }
        public static long[] Longs()
        {
            return Console.ReadLine().Split(' ').Select(s => long.Parse(s)).ToArray();
        }
        public static int[][] MultiInts(int num)
        {
            var result = new int[num][];
            for(int i = 0; i < num; ++i)
            {
                result[i] = Ints();
            }
            return result;
        }
        public static T[] MultiItems<T>(int num, Func<string,T> parser)
        {
            var result = new T[num];
            for(int i =0; i < num; ++i)
            {
                result[i] = parser(Console.ReadLine());
            }
            return result;
        }
    }
}


Measured memory_bytes: 13268
import java.util.*;

class Main {
    public static void main(String[] args) {
        new Solver().run();
    }
}

class Solver {
    public void run() {
        Scanner sc = new Scanner(System.in);
        int R = sc.nextInt();
        int G = sc.nextInt();
        int B = sc.nextInt();
        int N = sc.nextInt();

        int cnt = 0;
        for (int i = 0; i * R <= N; i++) {
            for (int j = 0 ; i * R + j * B <= N; j++) {
                int k = N - i * R - j * B;
                if (k % G == 0) {
                    cnt++;
                }
            }
        }
        System.out.println(cnt);

        return;
    }

}

Measured memory_bytes: 23764
N = list(input())

lastCharacter = int(N[len(N) - 1])

def print1():
	print('hon')

def print2():
	print('pon')

def print3():
	print('bon')

if lastCharacter == 2:
	print1()
elif lastCharacter == 4:
	print1()
elif lastCharacter == 5:
	print1()
elif lastCharacter == 7:
	print1()
elif lastCharacter == 9:
	print1()
elif lastCharacter == 0:
	print2()
elif lastCharacter == 1:
	print2()
elif lastCharacter == 6:
	print2()
elif lastCharacter == 8:
	print2()
else:
	print3()

Measured memory_bytes: 9136
#include<stdio.h>
#define N 10010
#define M 1000

int main(void){
  int i,num,j;
  int n,p,d1,d2;
  int sumd[N],maxd[M],ansp[M];

  for(i=0;;i++){
    scanf("%d",&n);
    if(n==0)
      break;
    for(j=0;j<N;j++){
      sumd[j]=0;
    }
    for(j=0;j<n;j++){
      scanf("%d%d%d",&p,&d1,&d2);
      sumd[p]+=(d1+d2);
    }
    maxd[i]=0;
    for(j=0;j<N;j++){
      if(maxd[i]<sumd[j]){
        maxd[i]=sumd[j];
        ansp[i]=j;
      }
    }
  }
  num=i;
  for(i=0;i<num;i++){
    printf("%d %d\n",ansp[i],maxd[i]);
  }
  return 0;
}

Measured memory_bytes: 416
using System;
using System.Linq;
using System.Collections.Generic;

public class Program
{
    static void Main()
    {
        //単体
        string line = Console.ReadLine().Trim();
        var luckyNumber = int.Parse(line);

        line = Console.ReadLine().Trim();
        var lockNumberList  = new Dictionary<int?, int?>();
        for (int i = 0; i < line.Length; i++)
        {
            lockNumberList.Add(i, int.Parse(line.Substring(i, 1)));
        }

        var resultList = CheckLockNumber(luckyNumber, lockNumberList);

        Console.WriteLine(resultList.Distinct().Count());
    }

    /// <summary>
    /// 暗証番号の組み合わせチェック※重複も含む
    /// </summary>
    /// <returns></returns>
    private static List<string> CheckLockNumber(int luckyNumber, Dictionary<int?, int?> lockNumberList)
    {
        var result = new List<string>();

        for (int i = 0; i < 10; i++)
        {
            var firstNumber = lockNumberList.FirstOrDefault(x => x.Key <= luckyNumber - 2 && x.Value == i);

            if (firstNumber.Key != null)
            {
                for (int j = 0; j < 10; j++)
                {
                    var secondNumber = lockNumberList.FirstOrDefault(x => x.Key > firstNumber.Key && x.Key <= luckyNumber - 1 && x.Value == j);

                    if (secondNumber.Key != null)
                    {
                        for (int k = 0; k < 10; k++)
                        {
                            var thirdNumber = lockNumberList.FirstOrDefault(x => x.Key > secondNumber.Key && x.Key <= luckyNumber && x.Value == k);

                            if (thirdNumber.Key != null) result.Add(firstNumber.Value.ToString() + secondNumber.Value.ToString() + thirdNumber.Value.ToString());
                        }
                    }
                }
            }
        }

        return result;
    }
}


Measured memory_bytes: 15584
#include<iostream>
using namespace std;
 
int main(){
    int n;
    cin >> n;
    int R[n];
    for ( int i = 0;i < n ;i++)cin >> R[i];
    int min = R[0];
    int a = R[1]-R[0];
    for ( int i = 1;i < n ;i++){
        if(min > R[i]){ min = R[i];
        }else if(min <= R[i] && a <= R[i]-min) a = R[i]-min;
    }
    cout << a <<endl;
     
    return 0;
}

Measured memory_bytes: 1940
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <functional>

using namespace std;

#define int long long

#define fst first
#define scd second
#define PB push_back
#define MP make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define omajinai ios::sync_with_stdio(false);cin.tie(0)
#define rep(i,x) for(int i=0;i<(int)(x);++i)
#define rep1(i,x) for(int i=1;i<=(int)(x);++i)

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

template<typename T>T& max(T&a,T&b){if(a>=b)return a;return b;}
template<typename T>T& min(T&a,T&b){if(a<b)return a;return b;}
template<typename T>bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<typename T>bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<typename T>T get(){T a;cin>>a;return a;}
template<typename T>T rev(T a){reverse(all(a));return a;}
template<typename T>vector<T>&sort(vector<T>&a){sort(all(a));return a;}

const int inf = (1ll << 31) - 1;
const ll linf = 3e18;
const double eps = 1e-9;

struct SegTree { // ??????min,max
    int n;
    vector<int> Max;
    vector<int> Min;

    void init(int n_)
    {
        n = 1;
        while (n < n_) n *= 2;

        Max.resize(2 * n);
        Min.resize(2 * n);

        for (int i = 0; i < 2 * n - 1; ++i) {
            Max[i] = -inf;
            Min[i] = inf;
        }
    }

    void min_update(int idx, int val)
    {
        idx += n - 1;
        Min[idx] = val;

        while (idx > 0) {
            idx = (idx - 1) / 2;
            Min[idx] = min(Min[idx * 2 + 1], Min[idx * 2 + 2]);
        }
    }

    void max_update(int idx, int val)
    {
        idx += n - 1;
        Max[idx] = val;

        while (idx > 0) {
            idx = (idx - 1) / 2;
            Max[idx] = max(Max[idx * 2 + 1], Max[idx * 2 + 2]);
        }
    }

    int get_min(int a, int b, int k = 0, int l = 0, int r = -1) // [a, b)???min
    {
        if (r == -1) r = n;

        if (r <= a || b <= l) return inf;

        if (a <= l && r <= b) return Min[k];

        int vl = get_min(a, b, k * 2 + 1, l, (l + r) / 2);
        int vr = get_min(a, b, k * 2 + 2, (l + r) / 2, r);

        return min(vl, vr);
    }

    int get_max(int a, int b, int k = 0, int l = 0, int r = -1) // [a, b)???max
    {
        if (r == -1) r = n;

        if (r <= a || b <= l) return -inf;

        if (a <= l && r <= b) return Max[k];

        int vl = get_max(a, b, k * 2 + 1, l, (l + r) / 2);
        int vr = get_max(a, b, k * 2 + 2, (l + r) / 2, r);

        return max(vl, vr);
    }
};

signed main()
{
    int N, Q; cin >> N >> Q;

    SegTree seg;
    seg.init(N);

    rep(i, Q) {
        int type, x, y; cin >> type >> x >> y;

        if (type == 0) {
            seg.min_update(x, y);
        } else {
            cout << seg.get_min(x, y + 1) << endl;
        }
    }
}

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

int main()	
{
	int m,f,r;
	while(cin >> m >> f >> r)
	{
		if(m == -1 && f == -1 && r == -1)
		{
			break;
		}

		if(m == -1 || f == -1) cout << "F" << endl;
		else if(m+f >= 80) cout << "A" << endl;
		else if(m+f >= 65) cout << "B" << endl;
		else if(m+f >= 50) cout << "C" << endl;
		else if(m+f >= 30)
		{
			if(r >= 50) cout << "C" << endl;
			else cout << "D" << endl;
		}
		else cout << "F" << endl;
	}
	return 0;
}

Measured memory_bytes: 1156
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#def gcd(m, n):
#    r = m % n
#    return gcd(n, r) if r else n

def lcm(a, b):
    return a * b // gcd(a,b)

N = int(input())
Ts = []
c = 1
for i in range(N):
    c = lcm(c, int(input()))

print(int(c))


Measured memory_bytes: 3060
def FB(n):
    if n%3==0 and n%5==0: return 'FizzBuzz'
    if n%3==0: return 'Fizz'
    if n%5==0: return 'Buzz'
    return str(n)

while True:
    M,N=map(int,input().split())
    if M==0 and N==0: break
    TF=[1]*M
    S=[input() for _ in range(N)]
    k=0
    for i,s in enumerate(S):
        if sum(TF)==1: break
        while True:
            if not TF[k]:
                k=(k+1)%M
            else:
                if FB(i+1)==s:
                    k=(k+1)%M
                    break
                else:
                    TF[k]=0
                    k=(k+1)%M
                    break
    ans=[]
    for j,p in enumerate(TF):
        if p:
            ans.append(str(j+1))
    print(' '.join(ans))

            

                





Measured memory_bytes: 7232
import sys; readline = sys.stdin.readline
from collections import deque

N = int(readline())
A = list(map(int, readline().split()))

l = 0
Mm = 0

total = sum(A)

for a in A:
    nl = l + a
    m = min(nl, total - nl)
    if m <= Mm:
        break
    else:
        Mm = m
    l = nl

print(total - Mm * 2)

Measured memory_bytes: 80848
#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
  int N ;
  std::cin >> N;
  std::vector<int> W(N);
  std::vector<int> diff(N);
  for(int i=0; i<N; i++) {
    std::cin >> W[i];
  }

  for(int t=0; t<N; t++) {
    for(int i=0; i<=t; i++) {
      diff[t] += W[i];
    }
    for(int i=t+1; i<N; i++) {
      diff[t] -= W[i];
    }
    if(diff[t] < 0) {
      diff[t] *= -1;
    }
  }

  std::cout << *std::min_element(diff.begin(), diff.end()) << std::endl;

  return 0;
}


Measured memory_bytes: 3584
import java.util.*;

public class Main{
    public static void main(String[] agrs){
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();
        int C = sc.nextInt();
        int X = sc.nextInt();

        int res = 0;
        for(int a = 0; a <= A; a ++){
            for(int b = 0; b <= B; b ++){
                int c = (X - 500 * a - 100 * b) / 50;
                if(c >= 0 && c <= C)
                res ++;
            }
        }
        System.out.println(res);
    }
}

Measured memory_bytes: 35704
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		try (Scanner s = new Scanner(System.in)) {
			final int L = s.nextInt();
			final int R = s.nextInt();

			if (R - L >= 2019) {
				System.out.println(0);
			} else {
				int ret = 2019;
				for (int i = L % 2019; i < R % 2019; i++) {
					for (int j = i + 1; j <= R % 2019; j++) {
						if ((i * j) % 2019 < ret) {
							ret = (i * j) % 2019;
						}
					}
				}
				System.out.println(ret);
			}
		}
	}
}


Measured memory_bytes: 21844
#include<bits/stdc++.h>
#include<vector>
#define LL long long
#define PI pair<LL,LL>
using namespace std;
LL D,St1[25],St2[25],P[25],Last[25],Ans;
vector<LL>V;
void DFS(LL L,LL R,LL Val,LL Cnt){
	if(L==R){
		Ans+=(Val==D)*Cnt;
		return; 
	}
	if(abs(Val-D)>Last[L]*10) return;
	for(LL I=-9;I<=9;I++){
		LL Ways=((L==0)?St2[I+10]:St1[I+10]);
		if(V[L]==0) Ways=(I<=0);
		if(Ways==0) continue;
		DFS(L+1,R,Val+I*V[L],Cnt*Ways);
	} 
}
void Solve(LL Len){
	V.clear();
	for(LL I=0;Len-I-1>=I;++I) V.push_back(P[Len-I-1]-P[I]);
	vector<PI>An1,An2;
	for(LL I=V.size()-1;I>-1;--I) Last[I]=Last[I+1]+V[I]; 
	DFS(0,V.size(),0,1);
}
int main(){
    scanf("%lld",&D);
    P[0]=1;
    for(LL I=1;I<=18;I++) P[I]=P[I-1]*10;
    for(LL I=0;I<=9;I++)
    	for(LL J=0;J<=9;J++){
    		St1[I-J+10]++;
			if(I&&J) St2[I-J+10]++;	
		}
	for(LL I=1;I<=18;I++) Solve(I);
	printf("%lld",Ans);
	return 0;
}


Measured memory_bytes: 3800
// IO library
#include <cstdio>
#include <iomanip>
#include <ios>
#include <iostream>

// algorithm library
#include <algorithm>
#include <cmath>
#include <numeric>

// container library
#include <deque>
#include <list>
#include <map>
#include <set>
#include <string>
#include <vector>

// namespace
using namespace std;

// typedef
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;

// container
#define EACH(i, c) for (auto i = (c).begin(); i != (c).end(); i++)
#define SORT(c) sort((c).begin(), (c).end())
#define GSORT(c) sort((c).begin(), (c).end(), greater<decltype((c).front())>())
#define SZ(x) ((int)(x).size())
#define MEMSET(c, v) memset((c), v, sizeof(c))

// repetition
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define NREP(i, n) FOR(i, 1, n + 1)
#define RFOR(i, a, b) for (int i = (a); i >= (b); i--)
#define RREP(i, n) RFOR(i, n, 0)
#define RNREP(i, n) RFOR(i, n, 1)

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

// debug
#define test(x) cout << #x << " = " << x << endl

// answer output
#define Yes(c) cout << ((c) ? "Yes" : "No") << endl;
#define YES(c) cout << ((c) ? "YES" : "NO") << endl;
#define possible(c) cout << ((c) ? "possible" : "impossible") << endl;
#define POSSIBLE(c) cout << ((c) ? "POSSIBLE" : "INPOSSIBLE") << endl;


// --------------------------------------------------------


int main()
{
    int N;
    cin >> N;
    VVI A(3, VI(N));
    REP(i, 3)
    {
        REP(j, N)
        {
            cin >> A[i][j];
        }
        GSORT(A[i]);
    }

    vector<ll> mnum(N, 0);
    int bitr = 0;
    REP(mitr, N)
    {
        if (mitr > 0) {
            mnum[mitr] = mnum[mitr - 1];
        }
        while (A[2][bitr] > A[1][mitr] && bitr < N) {
            mnum[mitr]++;
            bitr++;
        }
    }

    vector<ll> tnum(N, 0);
    int mitr = 0;
    REP(titr, N)
    {
        if (titr > 0) {
            tnum[titr] = tnum[titr - 1];
        }
        while (A[1][mitr] > A[0][titr] && mitr < N) {
            tnum[titr] += mnum[mitr];
            mitr++;
        }
    }

    cout << accumulate(tnum.begin(), tnum.end(), 0LL) << endl;
    return 0;
}

Measured memory_bytes: 2936
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
using namespace std;
#define int long long
#define REP(i,m,n) for(int i=(m);i<(n);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define all(a) a.begin(),a.end()
#define rall(c) (c).rbegin(),(c).rend()
#define mp make_pair
#define endl '\n'
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll inf=1e9+7;
const ll mod=1e9+7;
signed main(){
    ll n,m;cin>>n>>m;
    if(n%2){
    ll d=1;
    ll s=m*2+1;
    rep(i,m){
        cout<<d<<' '<<s-d<<endl;
        d++;
    }
    }else if(n%4==0){
        if(n/4<m){
            m-=n/4;
            ll d=1;
            ll s=n/2+1;
            rep(i,n/4){
                cout<<d<<' '<<s-d<<endl;
                d++;
            }
            d=n/2+1,s=d+n-1;
            rep(i,m){
                cout<<d<<' '<<s-d<<endl;
                d++;
            }
        }else{
            ll d=1;
            ll s=n/2+1;
            rep(i,m){
                cout<<d<<' '<<s-d<<endl;
                d++;
            }
        }
    }else{
        if(m>(n/2-1)/2){
            m-=(n/2-1)/2;
            ll d=1;
            ll s=n/2;
            rep(i,(n/2-1)/2){
                cout<<d<<' '<<s-d<<endl;;
                d++;
            }
            d=n/2,s=d+n-1;
            rep(i,m){
                cout<<d<<' '<<s-d<<endl;
                d++;
            }
        }else{
            ll d=1;
            ll s=n/2;
            rep(i,m){
                cout<<d<<' '<<s-d<<endl;;
                d++;
            }
        }
    }
}

Measured memory_bytes: 3640
N = int(input())
V = list(map(int,input().split()))
even = [0]*(10**5+10)
odd = [0]*(10**5+10)
for v in V[::2]:
  even[v] += 1
for v in V[1::2]:
  odd[v] += 1
max_even = max(even)
max_odd = max(odd)
if(even.index(max_even) != odd.index(max_odd)):
  print(N - max_even - max_odd)
else:
  even.sort(reverse = True)
  odd.sort(reverse = True)
  print(min(N - even[0] - odd[1], N - even[1] - odd[0]))

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

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

    int n;
    cin>>n;
    vector<ll> arr(n);
    for(int i=0; i<n; ++i){
        cin>>arr[i];
    }
    sort(arr.rbegin(), arr.rend());
    ll ans = arr[0];
    n -= 2;
    int ptr = 1;
    while(n){
        ans += arr[ptr];
        n--;
        if( n == 0 ){ break; }
        ans += arr[ptr];
        n--;
        ptr++;
    }
    cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 4780
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
#define base 196471
int n;
int main() {

	cin >> n;
	int Y, M, D;
	vector<int> ans;
	while (n--) {
		int tmp = 0;
		cin >> Y >> M >> D;
		tmp += (Y % 3 && !(M % 2)) ? 20 - D : 21 - D;
		for (int i = M+1; i <= 10; ++i) {
			tmp += (Y % 3 && !(i % 2)) ? 19 : 20;
		}
		for (int i = Y + 1; i <= 999; ++i) {
			tmp += (i % 3) ? 195 : 200;
		}
		ans.push_back(tmp);
	}
	for (int i = 0; i < ans.size(); ++i) {
		cout << ans[i] << endl;
	}
	return 0;
}


Measured memory_bytes: 3124
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvi std::vector<std::vector<int> >
#define vvl std::vector<std::vector<ll> >
#define MODs 1000000007;
typedef long long int ll;
using namespace std;

int main(int argc, char const *argv[]) {
  int N;
  std::cin >> N;
  vvi p = vv(N, N, 0, int);
  for(int i=0;i<N;i++) for(int j=0;j<N;j++) std::cin >> p[i][j];
  vvi dp = vv(N+1, 1<<21, 0, int);
  for(int i=0;i<N;i++) if(p[0][i]==1) dp[1][1<<i] = 1;
  for(int i=2;i<=N;i++){
    int comb = (1<<(i-1)) - 1;
    while(comb < 1 << N){
      int tmp = comb, now = 0;
      while(now<N){
        if(tmp%2==0&&p[i-1][now]==1) {
          dp[i][comb|(1<<now)] = (dp[i][comb|(1<<now)] + dp[i-1][comb])%1000000007;
          //std::cout << i <<" now " << now << " " <<(comb|(1<<now)) << '\n';
        }
        tmp/=2,now++;
      }
      int x = comb & -comb, y = comb+x;
      comb = ((comb & ~y) / x >> 1) | y;
    }
  }
  std::cout << dp[N][(1<<N)-1] << '\n';
  return 0;
}


Measured memory_bytes: 188800
#include <iostream>
using namespace std;
int main(){
    int y, m, d, i, times, D1, D2, D3;
    cin >> times;
    i = 0;
    while(1){i++;
        if(i>times){break;}
        cin >> y >> m >> d;
        D1 = (y-1)/3*200+((y-1)-(y-1)/3)*195;
        if(y%3==0){
            D2 = (m-1)*20+d;
        }
        else{
            D2 = (m-1)*20-(m-1)/2+d;
        }
        D3 = 196471 - D1 - D2;
        cout << D3 << endl;
    }
    
    return 0;

}

Measured memory_bytes: 1160
#include<iostream>
#include<map>

using namespace std;

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

    map<int, int> A;
    for(int i = 0; i < N; i++) {
        int num;
        cin >> num;
        if(A.find(num) == A.end()) {
            A.insert(make_pair(num, num));
        } else {
            A.erase(num);
        }
    }

    int ans = A.size();

    cout << ans << endl;

    return 0;
}

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

#define LL long long
int n, k, x;
set<int> s;

bool check(int x) {
    if(x < n) return 0;
    while(x > 0) {
        if(s.find(x % 10) != s.end()) return 0;
        x /= 10;
    }
    return 1;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    
    cin >> n >> k;
    while(k--) cin >> x, s.insert(x);  
    for(int i = 0; i <= 10000000; i++) {
        if(check(i)) {
            cout << i;
            return 0;
        }
    }  
}

Measured memory_bytes: 3592
N = int(input())
a = [int(i) for i in input().split()]

sunuke = 0
arai = sum(a)
ans = float('inf')

for i in range(N-1):
    sunuke += a[i]
    arai -= a[i]
    ans = min(ans, abs(arai-sunuke))

print(ans)

Measured memory_bytes: 24832
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<cstdio>
#include<sstream>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define all(in) in.begin(),in.end()
const double PI=acos(-1);
const double EPS=1e-8;
const int inf=1e9;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
int main(){
	int n,m;
	while(cin>>n>>m,n+m){
		vi a(n),b(m);
		rep(i,n){
			rep(j,16){
				int c;
				cin>>c;
				a[i]<<=1;
				a[i]+=c;
			}
		}
		rep(i,m){
			rep(j,16){
				int c;
				cin>>c;
				b[i]<<=1;
				b[i]+=c;
			}
		}
		vvi dp(n+1,vi(1<<16,-1));
		dp[0][0]=0;
		rep(i,n)rep(j,1<<16)if(dp[i][j]!=-1){
			int t=j|a[i];
			rep(k,m){
				int tt=t&b[k];
				int c=0;
				rep(l,16)if(1<<l&tt)c++;
				dp[i+1][t-tt]=max(dp[i+1][t-tt],dp[i][j]+c);
			}
		}
		int ma=-1;
		rep(i,1<<16)ma=max(ma,dp[n][i]);
		cout<<ma<<endl;
	}
}

Measured memory_bytes: 9452
# coding: utf-8
# Your code here!
r , g , b , n = map(int,input().split())
ans = 0
R = -(-n//r)
G = -(-n//g)
for i in range(R+1):
    for j in range(G+1):
        su = n-r*i-g*j
        if n-r*i-g*j < 0:
            break
        else:
            if (su/b).is_integer():
                ans += 1
print(ans)

Measured memory_bytes: 40556
def check(prev_, now_, S, N):
    rev = {'S':'W', 'W':'S'}
    prev, now = prev_, now_
    p  = [now]
    for i in range(1,N+1):
        if S[i] == 'o':
            if now == 'S':
                prev, now = now, prev
            else:
                prev, now = now, rev[prev]
        else:
            if now == 'S':
                prev, now = now, rev[prev]
            else:
                prev, now = now, prev
        p.append(now)
    if prev_ == prev and now_ == now:
        print(''.join(p[:-1]))
    return prev_ == prev and now_ == now

N=int(input())
S=input()
S = S[-1]+S+S[0]

ptn = ['SS', 'SW', 'WS', 'WW']
for sw in ptn:
    if check(sw[0], sw[1], S, N):
        break
else:
    print(-1)

Measured memory_bytes: 4992
// include
// ------------------------------------------------
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>

using namespace std;

// func
// ------------------------------------------------
int CalcSumOfDigit(int n);      // 各桁の和を計算する。

// define
// ------------------------------------------------
#define all(a)        (a).begin(),(a).end()
#define pb            push_back
#define sz(a)         int((a).size())
#define rep(i,n)      for(int(i)=0;(i)<(n);(i)++)
#define repe(i,n)     for(int(i)=0;(i)<=(n);(i)++)
#define vsort(v)      sort((v).begin(),(v).end())

// code
// ------------------------------------------------
int main() {
  int n;
  cin >> n;

  vector<int> t(n),x(n),y(n);

  rep(i,n)
  {
    cin >> t[i] >> x[i] >> y[i];
  }

  int ct = 0;
  int cx = 0;
  int cy = 0;
  bool can = true;

  rep(i,n)
  {
    int dt = t[i] - ct;
    int dx = x[i] - cx;
    int dy = y[i] - cy;

    if((dt - dx - dy) >= 0)
    {
      if((dt - dx - dy) % 2)
      {
        can = false;
        break;
      }
    }
    else
    {
      can = false;
      break;
    }
    


    ct = t[i];
    cx = x[i];
    cy = y[i];

  }

  if(can) cout << "Yes" << endl;
  else cout << "No" << endl;

  return 0;
}

// funcの実体
// ------------------------------------------------
int CalcSumOfDigit(int n)
{
  int s = 0;
  while(n)
  {
    s += n % 10;
    n = n / 10;
  }
  return s;
}

Measured memory_bytes: 1408
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int ncase;
vector<int> G[105];
int door[105];
vector<int> path;

int main(void)
{
	cin >> ncase;
	for(int nc = 0; nc < ncase; nc++){
		
		int room_id = 0, in;
		for(int i = 0; i < 105; i++) G[i].clear();
		path.clear(), path.push_back(0);
		
		while(1){
			cin >> in;
			if(in == 0) break;
			
			if(in > 0){
				room_id++;
				door[room_id] = in;
				if(path.back() != 0){
					G[room_id].push_back(path.back());
					door[room_id]--;
					G[path.back()].push_back(room_id);
					door[path.back()]--;
				}
				path.push_back(room_id);
			}
			else{
				int dest = path[path.size()+in-1];
				G[path.back()].push_back(dest);
				door[path.back()]--;
				G[dest].push_back(path.back());
				door[dest]--;
			}
			
			while( door[path.back()] == 0 && path.back() != 0 ){
				path.erase(path.end()-1);
			}
		}
		
		for(int i = 1; i <= room_id; i++){
			cout << i;
			sort(G[i].begin(), G[i].end());
			for(int j = 0; j < G[i].size(); j++) cout << " " << G[i][j];
			cout << endl;
		}
		
	}
	return 0;
}

Measured memory_bytes: 2996
public class
Main
{
  public void
  run (
    java.util.Scanner sc
    )
  {
    int[ ] a;
    int i, j;

    a = new int[ sc.nextInt ( ) ];
    for ( i = 0; i < a.length; ++i )
      a[ i ] = sc.nextInt ( );


    for ( i = 0; i < a.length; ++i )
    {
      final int t = a[ i ];
      for ( j = i - 1; j >= 0; --j )
      {
        if ( t < a[ j ] )
        {
          a[ j + 1 ] = a[ j ];
          a[ j ] = t;
        }
      }

      printArray ( a );
    }
  }

  private void
  printArray (
    int[ ] a
    )
  {
    int i;

    for ( i = 0; i < a.length; ++i )
    {
      System.out.print ( a[ i ] );
      if ( i + 1 < a.length )
        System.out.print ( " " );
      else
        System.out.println ( );
    }
  }

  public static void
  main (
    String[ ] args
    )
  {
    ( new Main ( ) ).run ( new java.util.Scanner ( System.in ) );
  }
}

Measured memory_bytes: 25924
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
int n, a[1000], dp[1000][1000];
int main() {
	while (true) {
		cin >> n; if (n == 0)break; for (int i = 0; i < 1000; i++) { for (int j = 0; j < 1000; j++)dp[i][j] = 0; }
		for (int i = 0; i < n; i++)cin >> a[i];
		for (int i = 0; i < n - 1; i++) { if (abs(a[i] - a[i + 1]) <= 1) { dp[i][i + 1] = 2; } }
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j <= n; j++) {
				int a1 = j, a3 = i + j; if (a3 >= n)continue;
				for (int k = a1 + 1; k <= a3; k++) {
					int a2 = k;
					dp[a1][a3] = max(dp[a1][a3], dp[a1][a2 - 1] + dp[a2][a3]);
				}
				if (dp[a1][a3] == i + 1 && a1 > 0 && a3 < n - 1 && abs(a[a1 - 1] - a[a3 + 1]) <= 1) {
					dp[a1 - 1][a3 + 1] = dp[a1][a3] + 2;
				}
			}
		}
		cout << dp[0][n - 1] << endl;
	}
	return 0;
}

Measured memory_bytes: 7012
#include<stdio.h>
#include<math.h>
#include<iostream>
using namespace std;
int main()
{
	int n, k, x, y;
	scanf("%d %d %d %d", &n, &k, &x, &y);
	if(n <= k)
		printf("%d\n", x * n);
		else
			printf("%d\n", x * k + (n - k) * y);
			return 0;
}

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

using namespace std;

int main() {
	long long W, H, x, y;
	cin >> W >> H >> x >> y;
	long long S;
	long long ans;
	S = W * H / 2;
	if (W % 2 == 1 && W % 2 == 1) cout << S << ".5" << " " << "0" << endl;
	else if (W % 2 == 0 && H % 2 == 0 && W / 2 == x && H / 2 == y) cout << S << " " << "1" << endl;
	else cout << S << " " << "0" << endl;
	return 0;
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Scan()
	var N int
	fmt.Sscanf(scanner.Text(), "%d", &N)

	ps := make([]int, N)
	for i := 0; i < N; i++ {
		scanner.Scan()
		fmt.Sscanf(scanner.Text(), "%d", &ps[i])
	}

	ans := 0
	sort.Sort(sort.Reverse(sort.IntSlice(ps)))
	for i := 0; i < len(ps); i++ {
		if i == 0 {
			ans = ans + ps[i]/2
		} else {
			ans = ans + ps[i]
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 640
#include <cstdio>
#include <cctype>
#include <utility>
#include <vector>
using namespace std;

#define _gp(l) const auto gcu{getchar##l}; const auto pcu{putchar##l}
#ifdef __linux
_gp(_unlocked);
#else
_gp();
#endif
#define _DEF(r, n, ...) inline r n(__VA_ARGS__) noexcept
#define _T template <typename T>
#define _HT template <typename H,typename... T>
_T _DEF(T,in,int c){T n=0;int m=1;while(isspace(c)){c=gcu();}if(c=='-')m=-1,c=gcu();
	do{n=10*n+(c-'0'),c=gcu();}while(c>='0'&&c<='9');return m*n;}
_DEF(int,in,){return in<int>(gcu());}
#define _SCAN(...) _DEF(bool,scan,__VA_ARGS__)
_T _SCAN(T &n){int c=gcu();return c==EOF?n=0,false:(n=in<T>(c),true);}
_SCAN(char &c){c=gcu();gcu();return c!=EOF;}
#ifdef _GLIBCXX_STRING
_SCAN(string &s){int c;s="";
	for(;;){c=gcu();if(c=='\n'||c==' ')return true;else if(c==EOF)return false;s+=(char)c;}}
#endif
_HT _SCAN(H &h,T&&... t){return scan(h)&&scan(t...);}
#define _OUT(...) _DEF(void,out,__VA_ARGS__)
#define _OUTL(...) _DEF(void,outl,__VA_ARGS__)
_OUT(bool b){pcu('0'+b);} _OUT(const char *s){while(*s)pcu(*s++);} _OUT(char c){pcu(c);}
#ifdef _GLIBCXX_STRING
_OUT(string s){for(char c:s)pcu(c);}
#endif
_T _OUT(T n){static char b[20];char *p=b;T m=n<0?pcu('-'),-1:1;
	if(!n)*p++='0';else while(n)*p++=(char)(n%10*m+'0'),n/=10;while(p!=b)pcu(*--p);}
_OUTL(){out('\n');}
#ifdef _GLIBCXX_VECTOR
_T _OUT(vector<T> v){for(T &x:v)out(&x == &v[0]?"":" "),out(x);}
#endif
_HT _OUT(H&& h, T&&... t){out(h);out(move(t)...);}
template <typename... T> _OUTL(T&&... t){out(move(t)...);outl();}
struct range{
	int e,b=0,s=1; range(int _b,int _e,int _s):e(_e),b(_b),s(_s){} range(int _b,int _e): e(_e), b(_b){} range(int _e):e(_e){}
	struct it { int v, s; it (int _v, int _s) : v(_v), s(_s) {} operator int()const{return v;} operator int&(){return v;} int operator*()const{return v;}
		it& operator++(){v+=s;return *this;} }; it begin() {return {b, s};} it end() {return {e, s};}};

int main() {
	int N {in()}, M {in()};
	vector<int> v(M), p(N);
	for (int &i: v)
		i = in() - 1;
	for (int i: v)
		for (int j: range(N))
			p[i == in() - 1 ? j : i]++;
	for (int i: p)
		outl(i);
}


Measured memory_bytes: 2552
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define INF (1LL<<59)
#define MV 200020
#define LMV 21
#define ff first
#define ss second
#define pb push_back
#define eb emplace_back
#define emp emplace
#define whoami(x) cerr<<#x<<" "<<x<<"\n";
#define mp make_pair
#define ins insert
#define sz size

void FLASH() {ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);}
void SETF() {cout.ios_base::setf(ios_base::fixed);}
void UNSETF() {cout.ios_base::unsetf(ios_base::fixed);}

typedef long long ll;
typedef long double ld;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef pair<PII, int> PPII;
typedef pair<PLL, ll> PPLL;
typedef map<int, int> MII;

const int MOD = 1000000007;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

struct h_llint {
  static uint64_t splitmix64(uint64_t x) {    // http://xorshift.di.unimi.it/splitmix64.c
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
};

struct h_pair{
  size_t operator()(const PLL&x)const{
    return hash<ll>()(((ll)x.ff)^(((ll)x.ss)<<32));
  }
};

typedef map<ll, ll> MLL;
typedef map<PII, int> MPII;
typedef map<PLL, ll> MPLL;
typedef set<int> SI;
typedef set<ll> SL;
//ordered_set = order_of_key(.)
//ordered_set = find_by_order(.)
typedef ordered_set<int> OSI;
typedef ordered_set<ll> OSL;
typedef ordered_multiset<int> MOSI;
typedef ordered_multiset<ll> MOSL;
typedef unordered_map<ll, int, h_llint> UMLI;
typedef unordered_map<ll, ll, h_llint> UMLL;
typedef unordered_map<PLL, int, h_pair> UMPI;
typedef unordered_map<PLL, ll, h_pair> UMPL;

int ar[MV];
bool vis[MV][4];
ll arr[MV], memo[MV][4];
int n;

ll xd(int ix, int yt)
{
	if(ix > n)
	return 0;
	if(vis[ix][yt])
	return memo[ix][yt];
	ll ans = arr[ix] + xd(ix+2, yt);
	if((yt > 0) && (ix+3 <= n))
	ans = max(ans, arr[ix] + xd(ix+3, yt-1));
	memo[ix][yt] = ans;
	vis[ix][yt] = 1;
	return ans;	
}

void solve(int T)
{
	memset(memo, 0, sizeof(memo));
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>arr[i];
	if(!(n & 1))
	{
		ll a1 = xd(1, 1);
		ll a2 = xd(2, 0);
		cout<<max(a1, a2)<<"\n";
	}
	else
	{
		ll a1 = xd(1, 2);
		ll a2 = xd(2, 1);
		ll a3 = xd(3, 0);
		cout<<max({a1, a2, a3})<<"\n";
	}
	return;
}

int main(void)
{
	FLASH();
	int T;
	T = 1;

// #ifndef ONLINE_JUDGE
// 	time_t time_t1, time_t2;
// 	time_t1 = clock();
// #endif

	//cin>>T;
	while(T--)
	solve(T);

// #ifndef ONLINE_JUDGE
// 	time_t2 = clock();
// 	SETF();
// 	cout<<"Time taken: "<<setprecision(7)<<(time_t2 - time_t1)/(double)CLOCKS_PER_SEC<<"\n";
// 	UNSETF();
// #endif

	return 0;
}

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

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

using namespace std;


int main() {

    int h,w; cin >> h >> w;
    char g[101][101];
    bool f = true;


    rep(i,h){
        rep(j,w){
            cin >> g[i][j];
        }
    }

    rep(i,h){
        f = true;
        rep(j,w){
            if(g[i][j] != '.'){
                f = false;
            }
        }
        if(f){
            rep(j,w){
                g[i][j] = 'b';
            }
        }
    }
    rep(i,w){
        f = true;
        rep(j,h){

            if(g[j][i] == '#'){
                f = false;
            }
        }
        if(f){
            rep(j,h){
                g[j][i] = 'b';
            }
        }
    }

    rep(i,h){
        f = true;
        rep(j,w){
            if(g[i][j] != 'b') {
                cout << g[i][j];
                f = false;
            }
        }
        if(!f) cout << endl;
    }

    return 0;
}











Measured memory_bytes: 3596
#include<iostream>
#include <cmath>
#include<string>
//#include <bits/stdc++.h>

typedef long double ld;
typedef long long ll;

using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
 //   freopen("input.txt","r",stdin);
   // freopen("output.txt","w",stdout);
    ll sum=0;int n;cin>>n;
    ll x;cin>>x; n--;
    while(n--){
        ll y; cin>>y;
        sum+=(x>y?x-y:0);
        x=max(x,y);
    }
    cout<<sum;
    return 0;
}

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

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << setprecision(20);

  int h, w;
  cin >> h >> w;
  vector<string> a(h);
  rep(i, h) cin >> a[i];

  vector<int> row_ok;
  rep(i, h) {
    bool ok = true;
    rep(j, w) {
      if (a[i][j] != '.') {
        ok = false;
        break;
      }
    }
    if (ok) row_ok.push_back(i);
  }

  vector<int> col_ok;
  rep(j, w) {
    bool ok = true;
    rep(i, h) {
      if (a[i][j] != '.') {
        ok = false;
        break;
      }
    }
    if (ok) col_ok.push_back(j);
  }

  rep(i, h) {
    if (find(row_ok.begin(), row_ok.end(), i) != row_ok.end()) continue;
    rep(j, w) {
      if (find(col_ok.begin(), col_ok.end(), j) != col_ok.end()) continue;
      cout << a[i][j];
    }
    cout << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N;
    cin >> N;
    vector<ll> d(N);
    for (ll i = 0; i < N; i++) {
        cin >> d[i];
    }
    sort(d.begin(), d.end());

    cout << d[N / 2] - d[N / 2 - 1] << endl;
}

Measured memory_bytes: 1024
from collections import deque
n, q = map(int, input().split())
Q = deque()
for i in range(n):
        name, time = input().split()
        Q.append([name, int(time)])

sum=0
            
while Q:
        qtime = Q.popleft()
        if qtime[1] <= q:
                sum =sum+ qtime[1]
                print(qtime[0], sum)
        else:
                sum =sum+ q
                qtime[1] =qtime[1]- q
                Q.append(qtime)


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

int isPrime(int x) {
  if (x < 2) return 0;
  else if (x == 2) return 1;
  
  if (x % 2 == 0) return 0;
  for (int i = 3; i * i <= x; i += 2) {
    if (x % i == 0) {
      return 0;
    }
  }
  return 1;
}

int main(void) {
  int X;
  cin >> X;

  int answer = X;
  while (!isPrime(answer)) {
    answer++;
  }

  cout << answer << endl;

  return 0;
}

Measured memory_bytes: 256
def c():
  from math import log2

  def get_ones(n):
    while n:
      k = n & -n
      yield int(log2(k))
      n ^= k

  N = int(input())
  guys = []
  for i in range(N):
    guys.append([])
    A = int(input())
    for j in range(A):
      guys[-1].append(tuple(map(int,input().split())))
  guys = guys[::-1]
  
  ans = 0
  for i in range(2**N):
    cnt = 0
    for j in get_ones(i):
      cnt += 1
      for k in range(len(guys[j])):
        if (int(i & (1 << (N - guys[j][k][0]))) != 0) != guys[j][k][1]:
          break
      else:
        continue
      break
    else:
      ans = max(cnt,ans)
  print(ans)
c()

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

int main() {
  long long n;
  long long a, b;
  long long ans;
  cin >> n;
  cin >> a >> b;
  if(a==0){
    ans=0;
  } else if(b==0){
    ans=n;
  } else{
    ans= (n/(a+b))*a;
    if(n%(a+b)>a){
      ans+=a;
    } else{
      ans+=n%(a+b);
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define FOR(i,a,b) for (register int i=a;i<=b;i++)
#define For(i,a,b) for (register int i=a;i>=b;i--)
#define mem(i,j) memset(i,j,sizeof(i))
#define GO(u) for (register int j=f[u];j!=-1;j=nxt[j])
using namespace std;
typedef long long ll;
const int N=2e6+5;
int n,a[N],Ans=0;
multiset <int> s;
multiset <int>::iterator it;
int read()
{
	int x=0,f=1;
	char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return f*x;
}
int main()
{
	n=read();
	FOR(i,1,n) a[i]=read();
	s.insert(a[1]);
	FOR(i,2,n)
	{
		it=s.lower_bound(a[i]);
		if (it==s.begin()) s.insert(a[i]),Ans++;
		else
		{
			it--;
			int tmp=*it;
			s.erase(s.find(tmp));
			s.insert(a[i]);
		}
	}
	printf("%d\n",Ans+1);
	return 0;
}
/*
6
1 1 2 2 3 3
*/

Measured memory_bytes: 5376
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
using namespace std;
long long cost[101],cap[101],n;
long long dp[101][100005];

long long knap(int i,int c){
    if(dp[i][c]!=-1) return dp[i][c];
    long long res;
    if(i==0 || c==0) res=0;
    else if(cap[i]>c) res=knap(i-1,c);
    else{
        long long t1,t2;
        t1=knap(i-1,c);
        t2=cost[i]+knap(i-1,c-cap[i]);
       // if(t2<0) cout << cost[i] << " " << knap(i-1,c-cap[i]) << " " << cost[i]+knap(i-1,c-cap[i]) << endl;
        //cout << t1 << " " << t2 << endl;
        res=max(t1,t2);
    }
  //  cout << i << " " << c << " " << res << endl;
   dp[i][c]=res;
    return res;
}
int main(){
    
        memset(dp,-1,sizeof(dp));
      
        long long c;
        cin >> n >> c;
       // cout << n << c << endl;
        for(int i=1;i<=n;i++){
            cin >> cap[i] >> cost[i] ;
           // cout << cap[i] << " " << cost[i] << endl;
        }
        
        cout << knap(n,c) << endl;
    
}

Measured memory_bytes: 82472
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <array>
#include <tuple>
#include <random>

using namespace std;
typedef long long int ll;

#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for(int i = int(a); i < int(b); i++)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep,)(__VA_ARGS__)
#define all(x) (x).begin(), (x).end()

#define inf 10000000000

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

    ll n, ans = 0;
    cin >> n;
    rep(i, 1, n + 1){
        ans += i;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256