akhauriyash/Code-Regression huggingface dataset:
// ProblemURL : https://atcoder.jp/contests/abc083/tasks/arc088_a
// ---------------------------------------------
package main

import "fmt"

func main() {
	var x, y int
	fmt.Scan(&x, &y)
	ans := 1
	for {
		if x*2 <= y {
			x *= 2
			ans++
		} else {
			break
		}
	}
	fmt.Println(ans)
}


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

using namespace std;
#define ll long long
const ll MAXN=1e8;
bool f[MAXN]={0};

int main()
{
    long long h,w;
    cin>>h>>w;
  if (h==1 || w==1)
    cout<<1;
  else
    cout<<(h*w+1)/2;
    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++)
#define all(v) v.begin(), v.end()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
using ll = long long;
const ll MOD = 1e9+7; int INF=INT_MAX; ll LLINF = 1LL << 60;
const vector<int> d8x = {1, 0, -1, 0, 1, -1, -1, 1}; vector<int> d8y = {0, 1, 0, -1, 1, 1, -1, -1};
const vector<int> d4x = {1, 0, -1, 0}; vector<int> d4y = {0, 1, 0, -1};

//

int main(){
    int n,w; cin>>n>>w;
    vector<ll> weight(n);
    vector<ll> value(n);
    rep(i,n){
        cin>>weight[i]>>value[i];
    }

    const int MAX_V = 100100;
    vector<vector<ll>> dp(n+1,vector<ll>(MAX_V, INF));
    
    dp[0][0]=0;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j <= MAX_V; j++)
        {
            chmin(dp[i+1][j],dp[i][j]);
            if (j - value[i] >= 0) chmin(dp[i+1][j], dp[i][j - value[i]] + weight[i]);
        }
    }

    long long res = 0;
    for (int sum_v = 0; sum_v < MAX_V; ++sum_v) {
        if (dp[n][sum_v] <= w) res = sum_v;
    }
    cout<<res<<endl;
    
}

Measured memory_bytes: 80256
n,m = map(int,input().split())

s = []
c = []

for i in range(m):
    si,ci = map(int,input().split())
    si-=1
    s.append(si)
    c.append(ci)

for ans in range(1000):
    x = str(ans)
    if len(x) != n :continue
    ok = True

    for i in range(m):
        for j in range(n):
            if (j == s[i])and(int(x[j]) != c[i]):ok = False
    
    if ok:
        print(ans)
        exit()

print(-1)


Measured memory_bytes: 3064
class Point():
    def __init__(self, x, y):
        self.x = x
        self.y = y

def main():
    n = int(input())
    Points = list()

    for _ in range(n):
        x, y = map(int, input().split())
        p = Point(x, y)
        Points.append(p)

    Points.sort(key=lambda x : x.y)
    Points.sort(key=lambda x : x.x)

    for p in Points:
        print(str(p.x) + " " + str(p.y))

main()



Measured memory_bytes: 30804
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;
using boost::multiprecision::cpp_int;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, int> pii;

const ll INF = LLONG_MAX;
const ll MOD = 1e9+7;

int main() {
    // input, ready
    int N;
    cin >> N;
    vector<ll> aList(N+1,0);
    for (int i=1; i<=N; i++) cin >> aList[i];

    // resolve
    map<ll, ll> mp;
    ll ans = 0;
    for (ll i=1; i<=N; i++) {
        mp[i-aList[i]]++;
    }
    for (ll i=1; i<=N; i++) {
        ans+=mp[aList[i]+i];
    }

    // output
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 27528
package main

import (
	"fmt"
)

func main() {
	var n, T int
	fmt.Scan(&n, &T)
	r := 1001
	for i := 1; i <= n; i++ {
		var c, t int
		fmt.Scan(&c, &t)
		if t <= T && c < r {
			r = c
		}
	}
	if r == 1001 {
		fmt.Println("TLE")
		return
	}
	fmt.Println(r)
}


Measured memory_bytes: 512
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <string>
#include <set>
#include <vector>
#include <queue>
#include <stack>
#include <map>
using namespace std;
#define ms(a, x) memset(a, x, sizeof(a))
#define fore(i, a, n) for (long long i = a; i < n; i++)
#define ford(i, a, n) for (long long i = n - 1; i >= a; i--)
#define si(a) scanf("%d", &a)
#define sl(a) scanf("%lld", &a)
#define sii(a, b) scanf("%d%d", &a, &b)
#define siii(a, b, c) scanf("%d%d%d", &a, &b, &c)
#define sll(a, b) scanf("%lld%lld", &a, &b)
#define slll(a, b, c) scanf("%lld%lld%lld", &a, &b, &c)
#define debug(a) cout << a << endl
#define pr(a) printf("%d ", a)
#define endl '\n'
#define pi acos(-1.0)
#define tr t[root]
#define lson t[root << 1]
#define rson t[root << 1 | 1]
#define IO ios::sync_with_stdio(false), cin.tie(0)
#define ull unsigned long long
#define py puts("Yes")
#define pn puts("No")
#define pY puts("YES")
#define pN puts("NO")
#define re(i, a, b) for (int i = a; i <= b; ++i)
#define de(i, a, b) for (int i = a; i >= b; --i)
const double eps = 1e-8;
inline int sgn(const double &x) { return x < -eps ? -1 : x > eps; }
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int MAXN = 1e5 + 5;
template <class T>
inline void cmin(T &a, T b) { ((a > b) && (a = b)); }
template <class T>
inline void cmax(T &a, T b) { ((a < b) && (a = b)); }
ll Ma[MAXN];
ll h[MAXN];
bool vis[MAXN];
int main()
{
  int n, m;
  sii(n, m);
  re(i, 1, n) sl(h[i]), Ma[i] = h[i];
  ll ans = n;
  re(i, 1, m)
  {
    ll a, b;
    sll(a, b);
    if (Ma[a] <= h[b] && vis[a] == 0)
      ans--,vis[a] = 1;
    if (Ma[b] <= h[a] && vis[b] == 0)
      ans--,vis[b] = 1;
  }
  cout << ans << endl;
}


Measured memory_bytes: 5344
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <limits>
#include <climits>
#include <utility>
#include <algorithm>
#include <numeric>

using namespace std;

using ll = long long;
using ull = unsigned long long;

int main()
{
    string a, b;
    cin >> a >> b;

    string s = a + b;
    int x = atoi(s.c_str());

    for (int i = 1; i <= 1000; ++i) {
        if (i * i == x) {
            cout << "Yes" << endl;
            return 0;
        }
    }

    cout << "No" << endl;

    return 0;
}


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

int main() {
  int N;
  cin >> N;
  vector<int> B(N - 1);
  int ans = 0;
  for(int i = 0; i < N - 1; i++) {
    cin >> B.at(i);
  }
  ans += B.at(0) + B.at(N - 2);
  for(int i = 1; i < N - 1; i++) {
    if(B.at(i - 1) > B.at(i)) {
      ans += B.at(i);
    }
    else {
      ans += B.at(i - 1);
    }
  }
  cout << ans << endl;
}

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

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

  vector<int> A(N), B(N), C(N - 1);
  for (int i = 0; i < N; i++) {
    cin >> A.at(i);
  }

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

  for (int i = 0; i < N - 1; i++) {
    cin >> C.at(i);
  }

  int before = -1;
  int ans = 0;
  for (int i = 0; i < N; i++) {
    ans += B.at(A.at(i) - 1);
    if (before != -1 && A.at(i) == before + 1) {
      ans += C.at(A.at(i) - 2);
    }
    before = A.at(i);
  }

  cout << ans << endl;
}

Measured memory_bytes: 256
use std::io;


fn read_line() -> String {
    let mut line = String::new();

    io::stdin().read_line(&mut line)
        .expect("Failed to read line");
    return line;
}
fn to_i(s: &str) -> i64 {
    return s.trim().parse()
        .expect("Please type a number!");
}
fn read_nums() -> Vec<i64>
{
    let line = read_line();
    let items: Vec<&str> = line.split(' ').collect();

    let mut nums: Vec<i64> = Vec::new();

    for item in items {
        nums.push(to_i(item));
    }
    return nums;
}


fn main() {
    let n: i64 = to_i( &read_line() );
    let s: Vec<char> = read_line().chars().collect();

    // let line = read_line();
    let k: i64 = to_i( &read_line() );

    let target = s[(k-1) as usize];

    let mut ret = String::new();
    for i in 0..n {
        let c  = s[i as usize];
        if c == target {
            ret += &c.to_string();
        } else {
            ret += "*";
        }
    }



    print!("{}", ret);
}   

Measured memory_bytes: 4352
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
#include<complex>
#include<numeric>
#include<bitset>
#define INF 1001001001
#define EPS 1e-8
#define x first
#define y second

using namespace std;
typedef vector<int> vint;
typedef vector<vint>  vvint;
typedef pair<int,int> pint;

int dx[4]={1,0,-1,0};
int dy[4]={0,-1,0,1};

//1541
int w,h;
int ans;

void saiki(int n,vvint cur,int x,int y){
	int i,j;
//	cout << x << "	" << y << endl;
	if(n>=ans) return;
	for(i=0;i<4;i++){
		if(cur[x+dx[i]][y+dy[i]]==1) continue;
		int nx=x;
		int ny=y;
		while(cur[nx][ny]==0){
			nx+=dx[i];
			ny+=dy[i];
		}
		int f=0;
		if(cur[nx][ny]==1){
			cur[nx][ny]=0;
			f=1;
		}
		if(cur[nx][ny]==3){
			ans=min(ans,n);
			return;
		}
		if(cur[nx][ny]==-1) continue;
		saiki(n+1,cur,nx-dx[i],ny-dy[i]);
		if(f==1) cur[nx][ny]=1;
	}
}

int main(){
	while(cin >> w >> h){
		if(w==0 && h==0) break;
		vvint mp(h+2,vint(w+2,-1));
		int i,j;
		int x,y;
		for(i=1;i<=h;i++){
			for(j=1;j<=w;j++){
				cin >> mp[i][j];
				if(mp[i][j]==2){
					x=i;
					y=j;
					mp[i][j]=0;
				}
			}
		}
		ans=11;
		saiki(1,mp,x,y);
		if(ans==11) cout << -1 << endl;
		else cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 960
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <list>
#include <queue>
#include <deque>
#include <algorithm>
#include <numeric>
#include <utility>
#include <complex>
#include <functional>
#include <climits>

using namespace std;

int gcd(int a, int b) {
    if(a < b) {
        int t = a;
        a = b;
        b = t;
    }
    if (b == 0) {
        return a;
    }
    return gcd(a % b, b);
}

int multigcd(vector<int> v) {
    for(size_t i = 0; i < v.size()-1; i++)
    {
        v[i+1] = gcd(v[i], v[i+1]);
    }
    return v[v.size()-1];
}

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

    int min = multigcd(a);
    cout << min << endl;
}



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

A,B,N = map(int, input().split())

if N >= B:
    x  = B - 1
    z = (A * x) // B - A * (x // B)
else:
    x = N
    z = (A * x) // B - A * (x // B)

print(int(z))

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

int comp(const void *a,const void *b){
  int *x=(int *)a;
  int *y=(int *)b;
  if (*x>*y) {
    return 1;
  }
  if (*x<*y) {
    return -1;
  }
  return 0;
}


 int main() {
  int n;
  float tab[50];
  memset(tab,1010,sizeof(tab));
  scanf("%d",&n);
  for (int i = 0; i < n; i++) {
    scanf("%f",&tab[i]);
  }
  qsort(tab,n,sizeof(int),comp);
  for (int i = 1; i < n; i++) {
    tab[i]=(tab[i]+tab[i-1])/2;
  }
  printf("%f\n",tab[n-1] );
   return 0;
 }


Measured memory_bytes: 128
import java.util.Scanner;

public class Main {


	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);
		String s = scan.next();
		String hitachi = "";
		boolean isHitachiString = false;
		for (int i = 0; i < 5; i++) {
			hitachi +="hi";
			if(s.equals(hitachi)) {
				isHitachiString = true;
				break;
			}
		}
		System.out.println(isHitachiString == true ? "Yes" : "No");
	}

}



Measured memory_bytes: 22868
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
int main() {
	int s,flag=0;
	int i = 0;
	cin >> s;
	int a[100000] = {0};
	a[0] = s;
	//cout << a[0] << endl;
	a[1] = (a[0]) / 2;
	//cout << a[1] << endl;
	i++;
	while (true) {
		
		//cout << i << endl;
		if (i == 0) {
			i += 2;
		}
		if ((a[i-1])% 2 == 0) {
			a[i] = (a[i-1]) / 2;
			//cout << a[i - 1] << endl;
			//cout << a[i] << endl;
		}
		else {
			a[i] = 3 * (a[i-1]) + 1;
			//cout << a[i-1] << endl;
			//cout << a[i] << endl;
		}
		for (int j = 0; j<i ; j++) {
			if (a[j] == a[i]) {
				//cout << i << endl;
				flag++;
				break;
			}
		}
		if (flag == 1) {
			break;
		}
		i++;
	}
	cout <<i+1 << endl;
}


Measured memory_bytes: 640
loop do
	x, op, y = gets.split
	a = x.to_i
	b = y.to_i

	case op
		when "+"
			puts a + b
		when "-"
			puts a - b
		when "*"
			puts a * b
		when "/"
			puts a / b
		when "?"
			break
	end
end

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

#http://drken1215.hatenablog.com/entry/2018/07/21/224200

# 条件の入力
N,M = map(int, raw_input().split())

orders=[]
for i in range(M):
	first, second = map(int, raw_input().split())
	orders.append((first, second))
	

#secondの値の小さい順に並び替え
cmpFunc = lambda x, y : x[1] - y[1]
sorted_orders = sorted(orders, cmpFunc)

#多分、この辺がgreedyにとっていく処理
ret=0
endtime=0
for order in sorted_orders:
	if order[0] >= endtime:
		endtime=order[1]
		ret+=1

#結果の出力
print ret


Measured memory_bytes: 18804
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ll long long int
const int INF = 2147483647;
const ll MOD = 1000000007;

using namespace std;

int main() {
  int a, b;
  cin >> a >> b;
  if (a < 10 && b < 10) {
    cout << a * b << endl;
  } else {
    cout << -1 << endl;
  }
}


Measured memory_bytes: 256
N = int(input())
sp_list = []
for line in range(N):
    S,P = input().split()
    P = int(P)
    sp_list.append([line+1,S,P])
sp_list = sorted(sp_list, key=lambda x:x[2], reverse=True)
sp_list = sorted(sp_list, key=lambda x:x[1])
for i in sp_list:
    print(i[0])

Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <iomanip>
#include <cmath>
#include <map>
#include <set>
#include <ctype.h>
#include <numeric>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
const ll MOD = 1e9 + 7;
const int INF = 1e9;

int dx4[4] = { 0, -1, 1, 0 };
int dy4[4] = { -1, 0, 0, 1 };
int dx8[8] = { 0, -1, 1, 0, -1, 1, -1, 1 };
int dy8[8] = { -1, 0, 0, 1, -1, -1, 1, 1 };

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

  cout << (a * b) / 2 << endl;
  return 0;
}


Measured memory_bytes: 764
#include<iostream>
#define rep(i,cc,n) for(int i=cc;i<=n;++i)
using namespace std;

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

  int p, q, l=0, r=N;
  rep(i,0,M-1) {
    cin >> p >> q;
    l = max(l, p);
    r = min(r, q);
  }

  cout << max(r - l + 1, 0) << endl;
  return 0;
}


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

signed main(){
    string S,T,U;
    int A,B;
    
    cin >> S >> T >> A >> B >> U;
    
    if(S==U) cout << A-1 << " " << B << endl;
    else cout << A << " " << B-1 << endl;
    
    return 0;
}



Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;
#define MAXN 300000
int prime[MAXN];/* i??????????´???° */
vector<pair<int,bool> > doyou(MAXN);
void sieve(int n){
  int i,j;
  for(i=j=0;i<n;i++){
    if(doyou[i].second){
      for(int k=i+1;k<n;k++)
        if(doyou[k].first%doyou[i].first==0) doyou[k].second=false;
    }
  }
}

int main(void){
  int n,i,j;
  int d[MAXN];
  int dnum;
  int a,b;
  int flag1,flag2;
  dnum=2;
  d[0]=6;d[1]=8;
  for(i=2;i<MAXN/2;i++){
    a=i*7-1;
    b=i*7+1;
    flag1=flag2=0;
    for(j=0;j<dnum;j++){
      if(a%d[j]==0) flag1=1;
      if(b%d[j]==0) flag2=1;
      if(flag1==1&&flag1==flag2) break;
    }
    if(flag1==0){
      d[dnum]=a;
      dnum++;
    }
    if(flag2==0){
      d[dnum]=b;
      dnum++;
    }
    if(a>MAXN) break;
  }
  while(cin>>n){
    if(n==1) break;
    cout<<n<<":";
    i=0;
    while(1){
      if(d[i]>n) break;
      if(n%d[i]==0) cout<<" "<<d[i];
      i++;
    }
    cout<<endl;
  }
  
  return 0;
}

Measured memory_bytes: 4964
///#pragma GCC optimize("Ofast")
///#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
///#pragma GCC optimize("unroll-loops")

#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;
///template<typename T> using orderset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

typedef long long ll;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vii> vvii;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<bool> vbb;

const ll N = 10000001;
const ll MOD = 1000000007;
const ll INF = LLONG_MAX;

#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rev(a) reverse(all(a))
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define yes cout<<"YES"<<nl
#define no cout<<"NO"<<nl
#define space ' '
#define nl '\n'
#define PI acos(-1)
#define Case(x) cout<<"Case "<<x<<": "
#define strtoint(a) atoi(a.c_str())

#define coutv(v) for(auto it:v)cout<<it<<space;cout<<nl;
#define cinv(v) for(auto &it:v)cin>>it;




int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    ll tc=1,cs=0;
    //cin>>tc;
    while(tc--)
    {
        int n,m,x,i,j,ans=INT_MAX;
        cin>>n>>m>>x;
        int v[n][m];
        vii c(n);
        for(i=0;i<n;i++)
        {
            cin>>c[i];
            for(j=0;j<m;j++)
                cin>>v[i][j];
        }
        for(i=1;i<(1<<n);i++)
        {
            vii tmp(m);
            int s=0;
            for(j=0;j<n;j++)
            {
                if((i&(1<<j)))
                {
                    s+=c[j];
                    for(int k=0;k<m;k++)
                        tmp[k]+=v[j][k];
                }
            }
            int mn=*min_element(all(tmp));
            if(mn>=x)
                ans=min(ans,s);
        }
        if(ans==INT_MAX)
            ans=-1;
        cout<<ans<<nl;
    }
}


Measured memory_bytes: 3660
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0,i##_len=(n);i<i##_len;++i)
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define All(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;

int main(){
    vector<int> A(3);
    REP(i,3) cin>>A[i];
    int K;cin>>K;
    sort(rbegin(A),rend(A));
    REP(i,K) A[0]*=2;
    cout<<A[0]+A[1]+A[2]<<endl;
}


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

using namespace std;

int main() {

	int s, N, sum = 0;
	cin >> N;
	int a[N];
	for (int i = 0; i < N; i++) {
		cin >> s;
		a[i] = s;
		sum += s;
	}
		
	sort(a, a + N);
	if (sum % 10 != 0) {
		cout << sum;
		return 0;
	}
	else {
		for (int j = 0; j < N; j++) {
			if (a[j] % 10 != 0) {
				cout << sum - a[j];
				return 0;
			}
		}
	}
	cout << 0;
	return 0;
}

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

#define ll long long
#define vvi vector<vector<int>>
#define vec vector
#define pq priority_queue
#define all(v) (v).begin(), (v).end()
#define rep(i, n) for (int (i) = (0); (i) < (n); ++(i))
#define repp(i, m, n) for (int (i) = (m); (i) < (n); ++(i))
#define debug(x) cerr << #x << ": " << x << endl;
#define debug2(x, y) cerr<<"("<<#x<<", "<<#y<<") = "<<"("<<x<<", "<<y<<")"<<endl;
#define debug3(x, y, z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = "<<"("<<x<<", "<<y<<", "<<z<<")"<<endl;
#define debugB(x, y) cerr<<#x<<": "<<bitset<y>(x) << endl;
#define line() cerr << "---------------" << endl;

const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};

template<typename T>
void printA(vector<T> &printArray, char between = ' ') {
   int paSize = printArray.size();
   for (int i = 0; i < paSize; i++) { cerr << printArray[i] << between;}
   if (between != '\n') {cerr << endl;}
}

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

int main() {
   int n;
   cin >> n;
   set<int> s;
   map<int, int> m;
   rep (i, n) {
      int x;
      cin >> x;
      s.insert(x);
      m[x]++;
   }

   for (auto x : m) {
      if (x.second >= 3) {
         if (x.second&1) {
            m[x.first] = 1;
         } else {
            m[x.first] = 2;
         }
      }
   }

   int cnt = 0;
   for (auto x : m) {
      if (x.second >= 2) cnt++;
   }
   if (cnt&1) {
      cout << m.size()-1 << endl;
   } else {
      cout << m.size() << endl;
   }

   return 0;
}

Measured memory_bytes: 9600
using System;
 
namespace Sample
{
  class Sample
  {
    static void Main(string[] args)
    {
    string[] str1=Console.ReadLine().Split(' ');
    string[] str2=Console.ReadLine().Split(' ');
      
      int N=int.Parse(str1[0]);
      long X=long.Parse(str1[1]);
      int d=0;
      int ans=1;
      for(int i=0;i<N;i++){
      d+=int.Parse(str2[i]);
        if(d>X){
          break;
        }
                ans++;

      }
      Console.WriteLine(ans);
    }
    
  }

}


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

using namespace std;

#define INF 100000000
#define YJ 1145141919
#define INF_INT_MAX 2147483647
#define INF_LL 9223372036854775
#define INF_LL_MAX 9223372036854775807
#define EPS 1e-10
#define MOD 1000000007
#define MOD9 998244353
#define Pi acos(-1)
#define LL long long
#define ULL unsigned long long
#define LD long double

#define int long long

using II = pair<int, int>;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(a)  begin((a)), end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())

signed main()
{
  string S;
  cin >> S;
  REP(n,S.size()-1) {
    if(S[n] == S[n+1]) {
      cout << "Bad" << endl;
      return 0;
    }
  }

  cout << "Good" << endl;

  return 0;
}

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

int main(){
  int N;cin>>N;
  int A[N];
  int X[N];
  for(int i=0;i<N;i++) cin>>A[i];
  ll sum=0;
  for(int i=0;i<N;i++){
    sum+=A[i];
  }
  sum/=2;
  for(int i=1;i<N;i+=2){
    sum-=A[i];
  }
  X[0]=sum;
  for(int i=0;i<N-1;i++){
    X[i+1]=A[i]-X[i];
  }
  for(int i=0;i<N;i++){
    cout<<2*X[i]<<(i==N-1?'\n':' ');
  }
  return 0;
}

Measured memory_bytes: 2048
#include <iostream>
#include <algorithm>

using namespace std;


int main(){
	int N;
	cin >> N;
	for(int i = 0;i < N;i++){
		int x ,y ,b ,p;
		cin >> x >> y >> b >> p;
		int sum = x * b + y * p;
		if(b < 5)
			b = 5;
		if(p < 2)
			p = 2;
		cout << min(sum ,int((x * b + y * p) * 0.8)) << endl;
	}
	return 0;
}


Measured memory_bytes: 1164
package main

import (
	"fmt"
)

func main() {
	var a,b,c int
	fmt.Scan(&a,&b,&c)

	m := make(map[int]int)
	m[a]++
	m[b]++
	m[c]++

	if m[5] == 2 && m[7] == 1 {
		fmt.Println("YES")
	} else {
		fmt.Println("NO")
	}
}


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

#define MAX_N 100000

int A[MAX_N];
int x[MAX_N];
int inv_c[MAX_N];

int main() {
  int N;
  cin >> N;
  for(int i=0; i<N; i++) {
    scanf("%d", &A[i]);
  }
  x[0] = 0;
  for(int j=0; j<N; j++) {
    x[0] += pow(-1, j%2) * A[j%N];
  }
  for(int i=1; i<N; i++) {
    x[i] = (A[i-1] - x[i-1]/2)*2;
  }
  printf("%d", x[0]);
  for(int i=1; i<N; i++) {
    printf(" %d", x[i]);
  }
  printf("\n");
  return 0;
}



Measured memory_bytes: 2048
#include <bits/stdc++.h>
#define rep(i, m, n) for(int i = m; i < (n); i++)
#define rrep(i,m,n) for(int i = m; i >= n; i--)
#define print(x) cout << (x) << endl;
#define print2(x,y) cout << (x) << " " << (y) << endl;
#define printa(x,n) for(int i = 0; i < n; i++){ cout << (x[i]) << " ";} cout << endl;
#define printa2(x,m,n) for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ cout << x[i][j] << " ";} cout << endl;}
#define printp(x,n) for(int i = 0; i < n; i++){ cout << "(" << x[i].first << ", " << x[i].second << ") "; } cout << endl;
#define INF (1e18)
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
typedef struct{
    ll to;
    ll cost;
} edge;
typedef pair<ll, ll> lpair;
ll N;
ll x[100010], y[100010];
vector<ll> tree[100010];
ll dp[100010][2] = {};
ll dfs(ll cur, ll par, ll color){
    ll &res = dp[cur][color];
    if(~res) return res;
    if(tree[cur].size() == 1 && cur != 0){
        res = 1;
        return 1;
    }
    res = 1;
    for(auto &e: tree[cur]){
        if(e == par) continue;
        ll tmp = 0;
        tmp += dfs(e, cur, 1) % MOD;
        if(color == 1){
            tmp += dfs(e, cur, 0) % MOD;
            tmp %= MOD;
        }
        res *= tmp;
        res %= MOD;
    }
    // if(cur == 0) print(res);
    return res;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N;
    rep(i,0,N-1){
        cin >> x[i] >> y[i];
        x[i]--; y[i]--;
        tree[x[i]].push_back(y[i]);
        tree[y[i]].push_back(x[i]);
    }
    if(N == 1){
        print(2);
        return 0;
    }
    memset(dp,-1,sizeof(dp));
    ll ans = (dfs(0, -1, 0) + dfs(0,-1, 1)) % MOD;
    print(ans);
}


Measured memory_bytes: 15872
a = int(input())
c = list(map(int, input().split()))
d = {0: 1}
e = 0
for i in range(len(c)):
    e += c[i]
    if e not in d:
        d[e] = 1
    else:
        d[e] += 1
ans = 0
for v in d.values():
    if v >= 2:
        ans += v * (v - 1) // 2
print(ans)


Measured memory_bytes: 39532
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  cin>>n;
  vector<int> ans(n);
  for (int i=0;i<n-1;i++){
    int num;
    cin >> num;
    ans.at(num-1)=ans.at(num-1)+1;
  }
      
  for (int i=0;i<n;i++){
     cout<<ans.at(i)<<endl;
  }
}

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

#define endl "\n"
#define all(x) x.begin(),x.end()
#define pb push_back
#define ff first 
#define ss second 
#define pii pair<int,int>
#define vi vector<int>
#define vc vector<char>
#define vii vector<pii>
#define vvi vector<vi>
#define fori(i,n) for(int i=1;i<=n;++i)
#define forn(i,n) for(int i=0;i<n;++i)
#define sz(x) int(x.size())
#define error(x) cout<<#x<<" "<<x<<endl
#define IOS  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

const int N=100*1000;
const int mod=1e9+7;

int min3(int a,int b,int c){return min(a,min(b,c));}
int max3(int a,int b,int c){return max(a,max(b,c));}
int min4(int a,int b,int c,int d){return min(min(a,b),min(c,d));}
int max4(int a,int b,int c,int d){return max(max(a,b),max(c,d));}

#define int int64_t
int a[N+2];

int32_t  main(){
	IOS;
  int ans=0;  
  int n,A,B;cin>>n>>A>>B;
  fori(i,n)cin>>a[i];
  for(int i=2;i<=n;++i)ans+=min((a[i]-a[i-1])*A,B);
  cout<<ans<<endl;
  return 0;

}



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


int main() {
  int N;
  cin >> N;
  ll last = 0;
  int cnt = 0;
  int max_c = 0;
  for (int i = 0; i < N; ++i) {
    ll hi;
    cin >> hi;
    if (i != 0) {
      if (hi <= last) {
        ++cnt;
        max_c = max(max_c, cnt);
      } else {
        cnt = 0;
      }
    }
    last = hi;
  }
  cout << max_c << endl;
}

Measured memory_bytes: 256
/*input

*/


//assic value of ('0'-'9') is(48 - 57) and (a-z) is (97-122) and (A-Z) is(65-90) and 32 for space
#include<bits/stdc++.h>
using namespace std;
#define ll          long long
#define pb          push_back
#define pii         pair<ll int,ll int>
#define vpii        vector< pii >
#define vi          vector<ll int>
#define vs			vector< string >
#define vvi         vector< vector< ll > >
#define inf			(ll)1e18
#define all(it,a)   for(auto it=(a).begin();it!=(a).end();it++) 
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define rep(i,a,b)	for(ll int i=a;i<b;i++)
#define repr(i,a,b) for(ll int i=a;i>b;i--)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define mp          make_pair
#define whatis(x)   cout << #x << " is " << x << "\n";
#define graph(n)    adj(n,vector< ll > () )
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll N = 3001,S=3001,mod=998244353;
ll n,s;
ll dp[N][S];
vi pf(S,0);
vi a;
int solve()
{
	cin>>n>>s;
	a.assign(n,0);
	rep(i,0,n) cin>>a[i];

	rep(i,0,n)
	{
		rep(j,a[i],S) dp[i][j] = (pf[j-a[i]]+(i+1)*(j==a[i]))%mod;
		rep(j,0,S) pf[j]=(pf[j]+dp[i][j])%mod;
	}

	ll ans=0;
	rep(i,0,n) ans=(ans+((n-i)*dp[i][s])%mod)%mod;

	cout<<ans<<"\n";


	return 0;
}

int main()
{
	auto start = chrono::high_resolution_clock::now();

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	ll test_cases=1;
	//cin>>test_cases;
	while(test_cases--)
		solve();

	auto stop = chrono::high_resolution_clock::now();
	auto duration = chrono::duration_cast<chrono::milliseconds>(stop-start);
	// cout<<"\nduration: "<<(double)duration.count()<<" milliseconds";
}

Measured memory_bytes: 70656
import math
s=int(input())
x1=0
y1=0
x2=int(math.sqrt(s))+1
x3=0
y2=0
y3=x2

if (x2-1)*(y3-1)==s:
    print(" ".join([str(x1),str(y1),str(x2-1),str(y2),str(x3),str(y3-1)]))
    exit()

else:
    x3=(x2-x1)*(y3-y1)-s
    y2=1
    ans=abs((x2-x1)*(y3-y1)-(x3-x1)*(y2-y1))
    print(" ".join([str(x1),str(y1),str(x2),str(y2),str(x3),str(y3)]))


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

#define LL long long
#define VI vector<int>
#define VB vector<bool>
#define VL vector<long long>
#define FOR(i,a,b) for(int i= (a); i<((int)b); ++i)
#define RFOR(i,a) for(int i=(a); i >= 0; --i)
#define FOE(i,a) for(auto i : a)
#define ALL(c) (c).begin(), (c).end()
#define RALL(c) (c).rbegin(), (c).rend()
#define DUMP(x)  cerr << #x << " = " << (x) << endl;
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v,x) (std::find(v.begin(), v.end(), x) != v.end())
#define BIT(n) (1LL<<(n))
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());
#define EPS 1e-14

const std::string YES = "YES";
const std::string Yes = "Yes";
const std::string NO = "NO";
const std::string No = "No";

bool inside(int y, int x, int H, int W) { return 0 <= y && y < H && 0 <= x && x < W; }

// 4近傍（右, 下, 左, 上）
const std::vector<int> dy = { 0, -1, 0, 1 };
const std::vector<int> dx = { 1, 0, -1, 0 };

using namespace std;


// 原点からの距離
int dist(int y, int x, int H, int W) {
    if (y == 0) { return x; }
    if (x == W) { return W + y; }
    if (y == H) { return W + H + (W - x); }
    return W + H + W + (H - y);
}

bool on_line(int y, int x, int R, int C) {
    return (x == 0 or x == R) or (y == 0 or y == C);
}

bool is_valid_parenthesis(vector<pair<int, int>> &v) {
    stack<int> s;
    for (auto p : v) {
        if (not s.empty()) {
            if (s.top() == p.second) { s.pop(); }   // 対応がとれた
            else { s.push(p.second); }
        }
        else {
            s.push(p.second);
        }
    }

    return s.empty();
}

bool solve(int R, int C, int N, vector<tuple<int, int, int, int>> &v) {

    vector<pair<int, int>> line;
    FOR(i, 0, N) {
        int x1, y1, x2, y2;
        tie(x1, y1, x2, y2) = v[i];

        if (on_line(y1, x1, R, C) and on_line(y2, x2, R, C)) {
            line.emplace_back(make_pair(dist(y1, x1, C, R), i));
            line.emplace_back(make_pair(dist(y2, x2, C, R), i));
        }
    }
    sort(ALL(line));
    return is_valid_parenthesis(line);
}

int main() {
    int R, C, N;
    cin >> R >> C >> N;

    vector<tuple<int, int, int, int>> v;
    FOR(i, 0, N) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        v.emplace_back(make_tuple(x1, y1, x2, y2));
    }

    cout << (solve(R, C, N, v) ? YES : NO) << endl;

    return 0;
}

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

#define FOR(i,l,r) for(int i = int(l);i < int(r);i++)
template<typename T> bool chmax(T& a,const T& b){ return a < b ? (a = b,true) : false; }
template<typename T> bool chmin(T& a,const T& b){ return b < a ? (a = b,true) : false; }
typedef long long ll;

int N,K;
const int MAX_N = 50;
pair<ll,ll> coor [MAX_N];
const ll INF = 5e18;

int main()
{
	cin >> N >> K;
	FOR(i,0,N){
		cin >> coor [i].first >> coor [i].second;
	}
	sort(coor,coor + N);

	ll ans = INF;
	FOR(i,0,N) FOR(j,0,N) FOR(k,0,N){
		ll y1 = min(coor [i].second,coor [j].second),y2 = max(coor [i].second,coor [j].second);
		ll x1 = coor [k].first,x2 = coor [k].first;
		int idx = lower_bound(coor,coor + N,make_pair(x1,-INF)) - coor;
		int cnt = 0;
		while(idx < N && cnt < K){
			if(coor [idx].second >= y1 && coor [idx].second <= y2){
				chmax(x2,coor [idx].first);
				cnt++;
			}
			idx++;
		}
		if(cnt == K){
			chmin(ans,(y2 - y1) * (x2 - x1));
		}
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <memory>
#include <complex>
#include <numeric>
#include <cstdio>
#include <iomanip>
#include <random>

#define REP(i,m,n) for(int i=int(m);i<int(n);i++)
#define RREP(i,m,n) for(int i=int(n)-1;i>=int(m);--i)
#define EACH(i,c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
//#define int long long

#ifdef LOCAL
#define DEBUG(s) cout << (s) << endl
#define dump(x)  cerr << #x << " = " << (x) << endl
#define BR cout << endl;
#else
#define DEBUG(s) do{}while(0)
#define dump(x) do{}while(0)
#define BR 
#endif
using namespace std;

using UI = unsigned int;
using UL = unsigned long;
using LL = long long;
using ULL = unsigned long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VVLL = vector<VLL>;
using VS = vector<string>;
using PII = pair<int,int>;
using VP = vector<PII>;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

bool solve(LL &t, VLL &a, LL &n, LL &k) {
    LL minv = 0;
    REP(i,0,n) {
        if (a[i] > 0) {
            int ok = i;
            int ng = n;

            while (abs(ok - ng) > 1) {
                long long mid = ng + (ok - ng) / 2;
                if (a[mid] * a[i] <= t) ok = mid;
                else ng = mid;
            }
            minv += ok - i;
            if (t == 0) dump(minv);
        } else if (a[i] < 0) {
            int ok = n;
            int ng = i;

            while (abs(ok - ng) > 1) {
                long long mid = ng + (ok - ng) / 2;
                if (a[mid] * a[i] <= t) ok = mid;
                else ng = mid;
            }
            minv += n - max(ok, i + 1);
            if (t == 0) dump(minv);
        } else {
            //if (t > 0) minv += n - i - 1;
            if (t >= 0) minv += n - i - 1;
            if (t == 0 || t == -16) dump(minv);
            if (t == 0) dump(minv);
        }
    }
    cerr << minv << ", " << t << endl;
    //return minv >= k - 1;
    return minv >= k;
}

long long meguru_bin(VLL &a, LL &n, LL &k) {
    long long ok = 1LL<<60;
    long long ng = -(1LL<<60);

    while (abs(ok - ng) > 1) {
        long long mid = ng + (ok - ng) / 2;
        if (solve(mid,a,n,k)) ok = mid;
        else ng = mid;
    }

    return ok;
}

void solve() {
    LL n,k;
    cin >> n >> k;
    VLL a(n);
    REP(i,0,n) cin >> a[i];
    sort(all(a));
    cout << meguru_bin(a,n,k) << endl;
}

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

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


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

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

#define fo(i, n) for(int i=0; i<n; i++)
#define Fo(i, k, n) for(int i=k; i<n; i++)
#define w(x)  int x; cin>>x; while(x--)
#define watch(x) cout << (#x) << " is " << (x) << "\n"
#define watch2(x,y) cout <<(#x)<<" is "<<(x)<<" and "<<(#y)<<" is "<<(y)<<"\n"
#define watch3(x,y,z) cout <<(#x)<<" is "<<(x)<<" and "<<(#y)<<" is "<<(y)<<" and "<<(#z)<<" is "<<(z)<<"\n"
#define watch4(x,y,z,q) cout <<(#x)<<" is "<<(x)<<" and "<<(#y)<<" is "<<(y)<<" and "<<(#z)<<" is "<<(z)<<" and "<<(#q)<<" is "<<(q)<<"\n"
#define MOD 1000000007
#define INF 1000000007;
#define F first
#define S second
#define pb(x) push_back(x);


#define ll  long long
#define all(c) (c).begin(),(c).end()
#define endl "\n"

typedef vector<int> vl;
typedef vector< vl > vvl;
typedef pair< int, int> pll;
typedef map< int, int> mll;


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





void c_p_c()
{
#ifndef ONLINE_JUDGE
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}
void parray(int a[],int n){
    for(int i=0;i<n;i++){
    cout<<a[i]<<" ";
    }
    cout<<endl;
}

int main() {
    int i,n,m,k,c=0,sum=0;
    c_p_c();
    cin>>n;
    int a[n];
    fo(i,n) cin>>a[i];
    sort(a,a+n);
    for (int i = 0; i < n-1; ++i)
    {
    	/* code */
    	sum+=a[i];
    }
    // sum+=a[n-1]/
    if(a[n-1]<sum)
    cout<<"Yes"<<endl;
	else
		cout<<"No"<<endl;
    return 0;
}



Measured memory_bytes: 3604
#include <stdio.h>

int main(void)
{
    int n, i;
    
    scanf("%d", &n);
    int a[n], b[n];
    
    for (i = 0; n > i; i++)
    {
        scanf("%d", &a[i]);
    }
    for (i = 0; n > i; i++)
    {
        b[n - i] = a[i];
    }
    
    for (i = 0; n > i; i++)
    {
        if (i)  printf(" ");
        printf("%d", b[i + 1]);
    }
    printf("\n");
    
    return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
using namespace std;
template<class C>constexpr int sz(const C&c){return int(c.size());}
using ll=long long;constexpr const char nl='\n',sp=' ';

const ll MOD = 1e9 + 7;

vector<ll> dp;

ll solve(int S) {
  if (S == 0) return 1;
  if (S < 3) return 0;
  if (dp[S] != -1) return dp[S];
  ll ret = 0;
  for (int i = 3; i <= S; i++) {
    ret += solve(S - i);
    if (ret >= MOD) ret -= MOD;
  }
  return dp[S] = ret;
}

int main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  // freopen("err.txt", "w", stderr);
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int S;
  cin >> S;
  dp.resize(S + 1, -1);
  cout << solve(S) << nl;
  return 0;
}


Measured memory_bytes: 3660
#include<bits/stdc++.h>
using namespace std;
const int N=1E3+7;
const int INF=1e9+7;
int mp[N][N];
int arr[N];
int n,m,k;
vector<int>ve;
int cal(int x,int y,int j){
    int sum=0;
    for(int i=x;i<=y;i++)
        sum+=mp[i][j];
    return sum;
}
int check(){
    int c=ve.size(),sum=0;
    for(int k1=1;k1<c;k1++) arr[k1]=0;
    bool flag=0;
    for(int j=1;j<=m;j++){
        for(int k1=1;k1<c;k1++){
            arr[k1]+=cal(ve[k1-1]+1,ve[k1],j);
            if(arr[k1]>k){
                sum++;
                flag=1;
                break;
            }
        }
        if(!flag) continue ;
        flag=0;
        for(int k1=1;k1<c;k1++){
            arr[k1]=cal(ve[k1-1]+1,ve[k1],j);
            if(arr[k1]>k) return INF;
        }
    }
    return sum;
}
int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char x;
            cin>>x;
            if(x=='1') mp[i][j]=1;
            else mp[i][j]=0;
        }
    }
    int c=(1<<(n-1))-1;
    int ans=INF;
    for(int i=0;i<=c;i++){
        ve.push_back(0);
        for(int j=0;j<n-1;j++)
            if((1<<j)&i) ve.push_back(j+1);
        ve.push_back(n);
        int x=ve.size();
        ans=min(ans,x-2+check());
        ve.clear();
    }
    cout<<ans<<endl;
    return 0;
}

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

using namespace std;

int main(){
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    if(a+b==c+d){
        cout<<"Balanced";
    }
    else if(a+b>c+d){
        cout<<"Left";
    }
    else {
        cout<<"Right";
    }
}


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

const int MAXN = 1e6 , Mod = 998244353;
int n , m , Ans , cnt[ MAXN + 5 ];

int k , prime[ MAXN + 5 ] , mu[ MAXN + 5 ] , f[ MAXN + 5 ];
bool vis[ MAXN + 5 ];
void sieve( ) {
    mu[ 1 ] = 1;
    for( int i = 2 ; i <= MAXN ; i ++ ) {
        if( !vis[ i ] ) {
            prime[ ++ k ] = i;
            mu[ i ] = -1;
        }
        for( int j = 1 ; j <= k && i * prime[ j ] <= MAXN ; j ++ ) {
            vis[ i * prime[ j ] ] = 1;
            if( i % prime[ j ] == 0 ) break;
            mu[ i * prime[ j ] ] = -mu[ i ];
        }
    }
    for( int i = 1 ; i <= MAXN ; i ++ )
        for( int j = i ; j <= MAXN ; j += i )
            f[ j ] = ( f[ j ] + i * mu[ i ] + Mod ) % Mod;
}

int main( ) {
    sieve( );
    scanf("%d",&n);
    for( int i = 1 , x ; i <= n ; i ++ ) {
        scanf("%d",&x) , Ans = ( Ans - x + Mod ) % Mod;
        cnt[ x ] ++ , m = max( m , x );
    }
    n = m;

    for( int i = 1 ; i <= n ; i ++ ) {
        int tmp = 0;
        for( int j = 1 ; j <= n / i ; j ++ )
            tmp = ( tmp + 1ll * cnt[ i * j ] * j % Mod ) % Mod;
        Ans = ( Ans + 1ll * i * f[ i ] % Mod * tmp % Mod * tmp % Mod ) % Mod;
    }

    printf("%d", 1ll * Ans * 499122177 % Mod );
    return 0;
}

Measured memory_bytes: 16216
H,W = map(int,input().split())
a = [list(map(int,input().split())) for i in range(H)]

ans = []

for i in range(H):
    if i%2:
        for j in range(W-1,0,-1):
            if a[i][j]%2:
                a[i][j] -= 1
                a[i][j-1] += 1
                ans.append([i+1,j+1,i+1,j])
        if i != H-1 and a[i][0]%2:
            a[i][0] -= 1
            a[i+1][0] += 1
            ans.append([i+1,1,i+2,1])

    else:
        for j in range(W-1):
            if a[i][j]%2:
                a[i][j] -= 1
                a[i][j+1] += 1
                ans.append([i+1,j+1,i+1,j+2])
        if i != H-1 and a[i][W-1]%2:
            a[i][W-1] -= 1
            a[i+1][W-1] += 1
            ans.append([i+1,W,i+2,W])
print(len(ans))
for an in ans:
    print(' '.join(map(str,an)))


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

int main() {
    int N; string S;
    cin >> N >> S;
    int sum = 0;
    int ans = 0;
    for (int i = 0; i < N; i++) {
        if (S[i] == 'I') {
            sum++;
        } else {
            sum--;
        }
        if (sum > ans) ans = sum;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
N,K = map(int,input().split())
X = []
for i in range(N):
    t,d = map(int,input().split())
    X.append((d,t))

X.sort(reverse=True)

p,v = 0,set([])
pp = []
for i in range(K):
    p += X[i][0]
    if X[i][1] not in v:
        v.add(X[i][1])
    else:
        pp.append((X[i][0],X[i][1]))

Ans = p + len(v)**2
ans = Ans
for i in range(K,N):
    if X[i][1] not in v and len(pp)>0:
        temp = pp[-1]
        pp = pp[:len(pp)-1]
        ans = ans - temp[0] + X[i][0] - len(v)**2 + (len(v)+1)**2
        v.add(X[i][1])
        Ans = max(Ans,ans)

print(Ans)


Measured memory_bytes: 21252
import java.util.*;

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

    String s = sc.next();
    String t = sc.next();
    int a = sc.nextInt();
    int b = sc.nextInt();
    String u = sc.next();

    if(u.equals(s)){
      a -= 1;
    } else if(u.equals(t)){
      b -= 1;
    }

    System.out.println(a + " " + b);
  }
}

Measured memory_bytes: 20820
#include <stdio.h>

int main(void){
  long long n,a[200005],sum=0,mod=1000000007,sinsum=0;
  scanf("%lld",&n);

  for(int i=1;i<=n;i++){
    scanf("%lld",&a[i]);
    sum+=a[i];
    sum%=mod;
  }
  for(int i=1;i<=n;i++){
    sum-=a[i];
    if(sum<0) sum+=mod;
    sum%=mod;
    sinsum+=a[i]*sum;
    sinsum=sinsum%mod;
  }
  printf("%lld\n",sinsum);

  return 0;
}



Measured memory_bytes: 3248
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(obj) (obj).begin(),(obj).end()
#define debug(x) cerr << #x << ": " << endl
#define rep(i,n) for(int i=0; (i)<(n); ++(i))
#define rrep(i,n) for(int i=(n); (i)>0; --(i))
#define reps(i,s,n) for(int i=(s); (i)<(n); ++(i))
#define maxi(v) distance(v.begin(), max_element(v.begin(), v.end()))
#define mini(v) distance(v.begin(), min_element(v.begin(), v.end()))
#define lb(v,x) v[lower_bound(v.begin(), v.end(), x) - v.begin()]
#define ub(v,x) v[upper_bound(v.begin(), v.end(), x) - v.begin()]
template<class T> inline bool print(T& x){ cout << x << endl; return true; }
template<class T> inline bool print_(T& x){ cout << x << " "; return true; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
ll gcd(ll x, ll y){
  if(y==0) return x;
  else return gcd(y, x%y);
  }
const int INF = 1e9;
const ll llINF = 1LL<<60;
const int MOD = 1e9+7;
const double EPS = 1e-9;

int main(){
    int n, s; cin >> n >> s;
    vector<int> x(n); rep(i,n) cin >> x[i];
    vector<int> diff(n); rep(i,n) diff[i] = abs(x[i]-s);
    int ans = diff[0];
    reps(i,1,n) ans = gcd(ans, diff[i]);
    
    cout << ans;
    
    return 0;
}



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

using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> vec(1e5+2, 0);
  for (int i = 0; i < n; ++i) {
    int a;
    cin >> a;
    ++vec[a];
  }

  int ans = 0;
  for (int i = 1; i <= 1e5; ++i)
    ans = max(ans, vec[i] + vec[i-1] + vec[i+1]);

  cout << ans << endl;
}



Measured memory_bytes: 3792
#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL)
#define ll long long
#define fm_t  ll t;cin>>t;while(t--)
#define fr(i,a,b) for( ll i=a;i<b;i++)
#define fr1(i,n,a) for( ll i=n-1;i>=a;i--)
#define sz(x) (ll)(x).size()
#define all(v)  (v).begin(), (v).end()
#define Sort(x) sort(x.begin(),x.end())
#define ms(a) memset(a,0,sizeof(a))
#define endl '\n'
#define pb push_back
#define ff first
#define ss second
const ll Mod = 998244353;
#define mod 1000000007

#define inf 1e18
#define ld long double
#define pll pair<ll, ll> 
#define vi vector<int>
#define vl vector<ll> 
#define vvl vector< vector<ll> > 
#define vvi vector< vector<int> >
#define vlp vector< pair<ll, ll> >
#define vllp vector<pair<ll, ll>, ll >
#define pi pair<ll, ll>
#define ppi pair<pair<ll, ll>, ll>
#define ump unordered_map<ll,ll>
#define pri priority_queue< pair<ll,ll> , vector< pair<ll,ll> >, greater< pair<ll,ll> > >
void ingraph(vl graph[], ll m){ll x, y;fr(i,0,m){cin>>x>>y;x--, y--;graph[x].pb(y);graph[y].pb(x);}}

#define max3(a, b, c)   max(max(a, b), c)
#define min3(a, b, c)   min(min(a, b), c)

//setprecision(10)
//greater<int>()
ll gcd(ll a, ll b){if(b==0)return a;return gcd(b, a%b);}
ll lcm(ll a, ll b){return a*b/gcd(a, b);}


ll modmulti(ll a, ll b){
   return ((a%mod)*1ll*(b%mod))%mod;
}
ll modadd(ll a, ll b){
   ll asdfgh =  ((a%mod)+(b%mod)+mod+mod)%mod;
   asdfgh = (asdfgh+mod)%mod;
   return asdfgh;
}
ll modpower(ll a, ll n){
   if(n==0) return 1;
   if(n==1) return a%mod;
   ll b = modpower(a,n/2);
   b = modmulti(b,b);
   if(n%2==0) return b;
   return modmulti(a,b);
}
ll modinv(ll a){
    return modpower(a,mod-2);
} 


     
int main()
{
      
  fast;
  ll n,k;
  cin>>n>>k;
  ll a[n+5];
  for(ll i=1;i<=n;i++)
      cin>>a[i];
  ll dp[n+1][k+1];
  ms(dp);
  dp[0][0]=1;
  for(int i=1;i<=n;i++)
  {
    ll pref[k+1];
    ms(pref);
    pref[0]=dp[i-1][0]%mod;
    fr(j,1,k+1)
      pref[j]=(pref[j-1]+dp[i-1][j])%mod;
    fr(j,0,k+1)
    {
      if(j<=a[i])
        dp[i][j]=pref[j]%mod;
      else dp[i][j]=(pref[j]-pref[j-a[i]-1]+mod)%mod;
    }
  } 

  cout<<dp[n][k]<<endl;


    
//cerr << "Time elapsed: " << clock() / (double)CLOCKS_PER_SEC << endl;
return 0;
}

Measured memory_bytes: 83268