akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define SaveTime ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back 
#define eb emplace_back
#define mx *max_element
#define mi *min_element
#define fn for(int i =0 ;i <n;i++)
#define fn1 for( int i =1;i<=n;i++)
#define fm for(int j =0 ;j <m;j++)
#define fm1 for(int j =1;j<=m;j++)
#define fi first
#define se second
#define MOD 1000000007
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
const int N = 1e6+5;
const int INF = 1e18L;
int ncr(int n,int r){if(n<r)return 0;int p=1,k=1;if(n-r<r)r=n-r;if(r!=0){while(r){p*=n;k*=r;int g=__gcd(p, k);p/=g;k/=g;n--;r--;}}else p=1;return p;}
#define pi 2*acos(0.0)
int ar[N];
int tree[2*N];
int dp[N];
int bit[N];
signed main(){
 	// #ifndef ONLINE_JUDGE
 	// freopen("input.txt","r",stdin);
 	// freopen("output.txt","w",stdout);
 	// #endif
	SaveTime;
	int T=1;
	// cin >> T;
	while(T--){
		int n;
		cin >> n;
		vector<int>v;
		for(int i =1;i*i<=n;i++){
			if(n%i==0){
				v.pb(i);
				if(n/i!=i)v.pb(n/i);
			}
		}
		sort(all(v));
		// for(auto i : v)cout << i<< " ";
		int sz = v.size();
		int st,en;
		if(sz&1){
			en = v[sz/2];
			st=en;
		}
		else{
			st=v[(sz-1)/2];
			en=v[(sz)/2];
		}
		cout << st+en -2 <<endl;
		// for(int i=1;i*i<=n;i++,cout<<endl){
		// 	for(int j=1;j*j<=n;j++){
		// 		cout << i*j << " " ;
		// 	}
		// }
	}
	
	return 0;
}


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

#define ed cout << "\n";
#define speed                         \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
#define ll long long
#define ffor(i, a, b) for (ll i = (ll)(a); i < (ll)(b); ++i)
#define rep(i, n) ffor(i, 0, n)
#define All(obj) (obj).begin(), (obj).end()
#define INF ((ll)1e9 + 7)
#define c(a) cout << a << "\n";
using namespace std;
const int N = 100005;

int main()
{
    speed;
    cout << fixed << setprecision(10);
    /*start*/
    ll n, a, b;
    cin >> n >> a >> b;
    if (a > b || (n <= 1 && a != b))
    {
        c(0);
        return 0;
    }
    ll misum = a * (n - 2);
    ll mxsum = b * (n - 2);
    c(mxsum - misum + 1);
    return 0;
}

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

int main() {
  int A,B;
  cin>>A>>B;
  if(A==B){
    cout<<"Draw"<<endl;}
  else if(A!=1&&B!=1){
    
    if(A>B){
      cout<<"Alice"<<endl;
    }else{cout<<"Bob"<<endl;}
    
  }else{
    if(A==1){
      cout<<"Alice"<<endl;
    }else{
      cout<<"Bob"<<endl;
    }
  }
}


Measured memory_bytes: 256
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
 
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
 
// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
 
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define f(i, n) for(int i = 0; i < n; ++i)
#define pb push_back
#define eb emplace_back
#define m_p make_pair
#define T int t = 0; cin >> t; while(t--)
#define pr(a) for(int i = 0; i < (int)a.size(); ++i)cout << a[i] << " ";cout << endl;
#define b_e(a) a.begin(), a.end()
typedef long long ll;
typedef long double lld;
const ll mod = 1e15;
const ll mx = 1e3 + 1;
const ll inf = 1e9;
const int sz = 256;
const int max_k = 20;
typedef long long ll;

void input(){
    IOS;
    int n;
    cin >> n;
    vector<int>a(n);
    f(i, n)cin >> a[i];
    int ans = 0;    
    for(int i = 0; i < n; ++i){
        for(int j = i + 1; j < n; ++j){
            if(a[j] == a[i])continue;
            for(int k = j + 1; k < n; ++k){
                if(a[k] == a[i] || a[k] == a[j])continue;
                if(a[i] + a[j] > a[k] && a[i] + a[k] > a[j] && a[j] + a[k] > a[i]){
                    ++ans;
                }
            }
        }
    }
    cout << ans << endl;
}

int main(){
    input();
    return 0;
} 
/*
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
*/


Measured memory_bytes: 3652
#include <stdio.h>
int main(){
    long long int a,b,k;
    scanf("%lld %lld %lld", &a, &b, &k);
    if(k<a){
        printf("%lld %lld", (a-k), b);
    }else if(a<=k && (k-a)<b){
        printf("0 %lld", (b-(k-a)));
    }else{
        printf("0 0");
    }
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#include <boost/range/irange.hpp>

using namespace std;
using boost::irange;
typedef long long ll;
const ll mod = 1e9 + 7;

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i: irange(0, N)) {
        cin >> A[i];
    }

    unordered_map<int, int> d;
    for (int i: irange(0, N)) {
        vector<int> cand{A[i] - 1, A[i], A[i] + 1};
        for (int &c: cand) {
            if (d[c]) {
                d[c]++;
            } else {
                d[c] = 1;
            }
        }
    }
    int ans = 0;
    for (auto kv: d) {
        ans = max(ans, kv.second);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4644
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <cmath>
using namespace std;
typedef long long i64;
typedef long double ld;
typedef pair<i64,i64> P;
#define rep(i,s,e) for(int i = (s);i <= (e);i++)

string s;
int k;

int next(char c)
{
    if(c == 'a') return 0;
    return ('z' - c + 1);
}

string str = "";

int main()
{
    for(char c = 'a';c <= 'z';c++)
    {
        str += c;
    }
    cin >> s >> k;

    rep(i,0,s.size() - 1)
    {
        int n = next(s[i]);
        if(n <= k)
        {
            s[i] = 'a';
            k -= n;
        }
    }

    k += s.back() -'a';

    s.back() = str[k % str.size()];

    cout << s << endl;
    return 0;
}

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

int main()
{
	int n, i, j, cnt = 0;
	char r[21];
	char b[11];
	scanf("%s", b);
	scanf("%d", &n);
	for (i = 0;i < n;i++) {
		scanf("%s", r);
		strcat(r, r);
		if (strstr(r, b) != NULL) {
			cnt += 1;
		}
	}
	printf("%d\n", cnt);
	return 0;
}

Measured memory_bytes: 612
#include<stdio.h>
#define N 100000
int binsea(int key,int A[],int n);
int main(){
  int a,b,c=0,i;
  int S[N],T[N];
  scanf("%d",&a);
  for(i=0;i<a;i++)scanf("%d",&S[i]);
  scanf("%d",&b);
  for(i=0;i<b;i++)scanf("%d",&T[i]);
  for(i=0;i<b;i++){
  c+=binsea(T[i],S,a);
  }
  printf("%d\n",c);
}
int binsea(int key,int A[],int n){
  int l=0,r=n,m;
  while(l<r){
    m=(l+r)/2;
    if(A[m]==key)return 1;
    else if(A[m]>key)r=m;
    else l=m+1;
  }
    return 0;
}



Measured memory_bytes: 2316
n, m, k = map(int, input().split())
mod = 998244353

N = 10**6  # N!まで求める
fact  = [1, 1]  # 階乗の元テーブル
fact_inv = [1, 1]  # 階乗の逆元テーブル
inv = [0, 1]  # 逆元テーブル計算用テーブル 1,2,,...の逆元を求めてる

# 計算 O(1)
def comb(n, r, mod):
    if (r<0 or r>n):
        return 0
    r = min(r, n-r)
    return fact[n] * fact_inv[r] * fact_inv[n-r] % mod

# 順列
def perm(n, r, mod):
    if (r<0 or r>n):
        return 0
    return fact[n] *  fact_inv[n-r] % mod

# 前処理 O(n)
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod//i)) % mod)
    fact_inv.append((fact_inv[-1] * inv[-1]) % mod)

ans = 0
for i in range(k+1):
    ans += comb(n-1, i, mod) * m * pow(m-1, n-i-1, mod)
    ans %= mod

print(ans)

Measured memory_bytes: 127596
#include <stdio.h>

int main(){
  int i,j,minj,n,A[100],x,count=0;

  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
  }
 
  for(i=0;i<n;i++){
    minj = i;
    for(j=i;j<n;j++){
      if(A[j]<A[minj]){
	minj = j;
      }
    }
    x = A[i];
    A[i] = A[minj];
    A[minj] = x;
    if(i != minj)count++;
  }
  for(i=0;i<n;i++){
    printf("%d",A[i]);
    if(i!=n-1)printf(" ");
  }
  printf("\n%d\n",count);
  return 0;
}



Measured memory_bytes: 2104
import java.util.ArrayList;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = Integer.parseInt(sc.next());
		ArrayList<Integer> list = new ArrayList<>();
		for(int i = 0; i < N; i++) {
			list.add(Integer.parseInt(sc.next()));
		}
		sc.close();

		boolean check = true;

		//条件分岐
		for(int i = 0; i < list.size(); i++) {
			int number = list.get(i);
			if(number % 2 != 0) {
				continue;
			}else if(number % 6 == 0 || number % 10 == 0) {
				continue;
			}else {
				System.out.println("DENIED");
				check = false;
				return;
			}

		}
		if(check) System.out.println("APPROVED");

	}
}


Measured memory_bytes: 21972
#include<bits/stdc++.h>  
using namespace std;  
     
int w, h, n;  
char mas[20][20];  
int change[10];
typedef pair< int , int > Pi;  
typedef pair< Pi , Pi > Piii;
typedef pair< Piii, int > Piiii;
Pi p;  
     
struct sell{  
  int d; //値引き額  
  int s; //開始時刻  
  int e; //終了時刻  
};  
sell shop[10];  
     
int min_cost[20][20][1 << 10];
     
int bfs(){  
  priority_queue< Piiii, vector< Piiii >, greater< Piiii > > que; // Pii( (買った商品, 今の時間), 座標)  
  const int dy[] = { 1, 0, -1, 0}, dx[] = { 0, 1, 0, -1};  
     
  memset( min_cost, -1, sizeof(min_cost));  
  que.push( Piiii( Piii( Pi( 0, 0), p), 0));  
  min_cost[p.second][p.first][0] = 0;  
     
  int ret = 0;  
     
  while(!que.empty()){  
     
    Piiii p = que.top(); que.pop();  
     
    Pi point = p.first.second;  
    int bit = p.first.first.second, time = p.first.first.first;
    int cost = p.second;

    for(int i = 0; i < 4; i++){
      int ny = point.second + dy[i], nx = point.first + dx[i];  
      if(ny < 0 || ny >= h || nx < 0 || nx >= w) continue;
      if(!isdigit(mas[ny][nx])) continue;
      int pos = change[mas[ny][nx] - '0'];
      if(pos == -1) continue;
      if(shop[pos].s <= time && time < shop[pos].e && !((bit >> pos) & 1)){
        bit |= (1 << pos);
        cost += shop[pos].d;
      }
    }
    if(cost < min_cost[point.second][point.first][bit]){
      continue;
    }
    min_cost[point.second][point.first][bit] = max( cost, min_cost[point.second][point.first][bit]);

    
    if(ret < min_cost[point.second][point.first][bit]){  
      ret = min_cost[point.second][point.first][bit];  
    }  
     
    for(int i = 0; i < 4; i++){  
      int ny = point.second + dy[i], nx = point.first + dx[i];  
      if(ny < 0 || ny >= h || nx < 0 || nx >= w) continue;  
     
      if(isdigit(mas[ny][nx])){  
        int time_sell = change[mas[ny][nx] - '0'];
        if(time_sell == -1) continue;
        if(!((bit >> time_sell) & 1)){
          sell se = shop[time_sell];
          if(se.s > time){
            que.push( Piiii( Piii( Pi( se.s, bit), point), cost));
          }
        }    
      } else {  
        if(min_cost[point.second][point.first][bit] > min_cost[ny][nx][bit]){ 
          que.push( Piiii( Piii( Pi( time + 1, bit), Pi( nx, ny)), cost));  
          min_cost[ny][nx][bit] = min_cost[point.second][point.first][bit];  
        }  
      }  
    }  
  }  
  return ret;  
}  
     
int main(){  
  while(cin >> w >> h, w){  
    for(int i = 0; i < h; i++){  
      for(int j = 0; j < w; j++){  
        cin >> mas[i][j];  
        if(mas[i][j] == 'P') p = Pi( j, i);  
      }  
    }  
    cin >> n;  
    memset( change, -1, sizeof(change));
    for(int i= 0; i < n; i++){  
      int g;  
      cin >> g;  
      cin  >> shop[i].d >> shop[i].s >> shop[i].e;
      change[i] = g;
    }
     
    cout << bfs() << endl;  
  }  
}  

Measured memory_bytes: 3012
#include <bits/stdc++.h>
using namespace std;
#define int lint
typedef long long lint;
typedef pair<int,int> P;
const int    INF=(int)1e9;
const int    MOD=(int)1e9+7;
const double EPS=(double)1e-10;
struct Accelerate_Cin{
    Accelerate_Cin(){
        cin.tie(0); ios::sync_with_stdio(0);cout<<fixed<<setprecision(20);
    };
};



signed main(){
  int N;
  cin>>N;
  int temp=N;

  int sum=0;
  while(N>0){
    sum+=N%10;
    N/=10;
  }

  if(temp%sum==0){
    cout<<"Yes"<<"\n";
  }else{
    cout<<"No"<<"\n";
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FAST_INPUT ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ll long long

using namespace std;





void solve() {
	int n;
	cin >> n;
	vector<int> h(n), a(n);
	for (int i = 0; i < n; i++) {
		cin >> h[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}


	int base = 1;
	while (base <= n) {
		base *= 2;
	}
	vector<ll> tree(2 * base);


	vector<ll> dp(n + 1);
	for (int i = 0; i < n; i++) {
		// max dp[j] for j in [0, h[i] - 1]

		int x = h[i] + base;
		ll best = 0;
		while (x > 1) {
			if (x % 2 == 1) {
				best = max(best, tree[x - 1]);
			}
			x /= 2;
		}

		dp[h[i]] = best + a[i];

		for (int j = base + h[i]; j >= 1; j /= 2) {
			tree[j] = max(tree[j], dp[h[i]]);
		} 

		// for (int j = 0; j < h[i]; j++) {
		// 	dp[h[i]] = max(dp[h[i]], dp[j] + a[i]);
		// }
	}


	ll res = -1;
	for (int i = 0; i <= n; i++) {
		res = max(res, dp[i]);
	}

	cout << res << endl;
}

int main() {
    FAST_INPUT;

    solve();
    return 0;
}


Measured memory_bytes: 7552
#define _CRT_SECURE_NO_WARNINGS
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define int ll
//#define endl "\n"
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
#define all(c) (c).begin(), (c).end()
#define loop(i,a,b) for(ll i=a; i<ll(b); i++)
#define rep(i,b) loop(i,0,b)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
template<class T> ostream & operator<<(ostream & os, vector<T> const &);
template<int n, class...T> typename enable_if<(n>=sizeof...(T))>::type _ot(ostream &, tuple<T...> const &){}
template<int n, class...T> typename enable_if<(n< sizeof...(T))>::type _ot(ostream & os, tuple<T...> const & t){ os << (n==0?"":" ") << get<n>(t); _ot<n+1>(os, t); }
template<class...T> ostream & operator<<(ostream & os, tuple<T...> const & t){ _ot<0>(os, t); return os; }
template<class T, class U> ostream & operator<<(ostream & os, pair<T,U> const & p){ return os << "(" << p.first << ", " << p.second << ") "; }
template<class T> ostream & operator<<(ostream & os, vector<T> const & v){ rep(i,v.size()) os << v[i] << (i+1==(int)v.size()?"":" "); return os; }
template<class T> inline bool chmax(T & x, T const & y){ return x<y ? x=y,true : false; }
template<class T> inline bool chmin(T & x, T const & y){ return x>y ? x=y,true : false; }
#ifdef DEBUG
#define dump(...) (cerr<<#__VA_ARGS__<<" = "<<mt(__VA_ARGS__)<<" ["<<__LINE__<<"]"<<endl)
#else
#define dump(...)
#endif
// ll const mod = 1000000007;
// ll const inf = 1LL<<60;

int D,N;
int a[111], e[111], r[111];
int INF = INT_MAX/4;
int dp[111][111];
int solve(int d, int exp){
    if(d == D) return 0;
    int & res = dp[d][exp];
    if(res != -1) return res;
    res = INF;
    rep(i,N){
        int dd = min(D,d+a[i]), ee = min(100,exp+e[i]);
        if((dd==d && ee==exp) || r[i] > exp) continue;
        res = min(res, 1+solve(dd,ee));
    }
    return res;
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    while(cin >> D >> N && D){
        rep(i,N){
            cin >> a[i] >> e[i] >> r[i];
            if(a[i]==0 && e[i]==0) r[i] = INF;
        }
        memset(dp,-1,sizeof(dp));
        int ans = solve(0,0);
        if(ans >= INF/10) cout << "NA";
        else cout << ans;
        cout << endl;
    }
}

Measured memory_bytes: 1264
#include <stdio.h>
#include <math.h>
const double eps=1e-9;
struct Circle{
	double x,y,r;
};
typedef struct Circle Circle;
Circle input(){
	Circle ret;
	scanf("%lf %lf %lf",&ret.x,&ret.y,&ret.r);
	return ret;
}
double distance(Circle a,Circle b){
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

int main(){
	int n;	scanf("%d",&n);
	while(n--){
		Circle a=input(),b=input();
		double dist=distance(a,b);
		if(a.r-dist-b.r>eps)	printf("2\n");
		else if(b.r-dist-a.r>eps)	printf("-2\n");
		else if(a.r+b.r-dist>-eps)	printf("1\n");
		else 	printf("0\n");
	}
	return 0;
}
			

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

const int N = 2e5 + 10 , mod = (int)1e9 + 7 ; 

int n , a[N] , dp[N] , sum[N] ; 

int32_t main() {
	cin >> n ; 
	for(int i = 1 ; i <= n ; ++i)
		cin >> a[i] ; 
	dp[0] = 1 ; 
	for(int i =  1 ; i <= n ; ++i) { 
		dp[i] = dp[i - 1] ; 
		if(a[i] != a[i - 1]) { 
			dp[i] += sum[a[i]] ; 
			sum[a[i]] += dp[i - 1] ; 
			dp[i] %= mod ; 
			sum[a[i]] %= mod ; 
		}
	}
	cout << dp[n] << endl ; 
}


Measured memory_bytes: 2560
#include <cstdio>
#include <stdlib.h>
#include <ctype.h>
#include <cstring>
#include <math.h>
#include <limits.h>

typedef struct {
    long long int A;
    long long int number;
} person;
int cmpnum(const void * n1, const void * n2)
{
    if (*(long long *)n1 < *(long long *)n2)
    {
        return 1;
    }
    else if (*(long long *)n1 > *(long long *)n2)
    {
        return -1;
    }
    else
    {
        return 0;
    }
}

int max(long long int n1, int long long n2){
    if (n1 < n2){
        return n2;
    }
    else{
        return n1;
    }
}



int main() {

    long long int N;


    scanf("%lld", &N);



    person person1[N];
    for (long long int i = 0; i < N; ++i) {
        scanf("%lld", &person1[i].A);
        person1[i].number = i;
    }
    qsort(person1, sizeof(person1) / sizeof(person1[0]), sizeof(person), cmpnum);


    long long int DP[N + 10][N + 10];
    long long int max_s = 0;
    DP[0][0] = 0;
    for(int i = 0; i <= N; ++i){
        for(int j = 0; j <= N; ++j){
            DP[i][j] = 0;
        }
    }


    for(long long int i = 0; i < N; ++i) {
        for (long long int j = 0; i + j + 1 <= N; ++j) {
            if(DP[i+1][j] < DP[i][j] + person1[i+j].A * (person1[i+j].number-i)) {
                DP[i + 1][j] = DP[i][j] + person1[i + j].A * (person1[i + j].number - i);
            }
            if(DP[i][j+1] < DP[i][j] + person1[i+j].A *(N-1-j-person1[i+j].number)) {
                DP[i][j + 1] = DP[i][j] + person1[i + j].A * (N - 1 - j - person1[i + j].number);
            }
//            printf("%lld,%lld\n", DP[i+1][j], DP[i][j+1]);
        }
    }

    for(int i = 0; i <= N; ++i){
            if(DP[i][N-i] > max_s){
                max_s =DP[i][N-i];
            }
    }
    printf("%lld\n",max_s);
    return 0;
}



int D_4_19(){

long long int N;
long long int K;
long long int S1 = 0;
long long int S2 = 0;
long long int SUM = 0;
long long int MOD = 1000000007;


scanf("%lld %lld",&N,&K);

for(long long int k = K  ; k <= N+1 ; ++k){

S1 = ( (k)*(k-1)/2 ) ;

S2 = (k* (N + N - k + 1) / 2 ) ;
//        printf("%ld\n",S1);
//        printf("%ld\n",S2);
SUM += S2 -S1 + 1;
//        printf("%lld\n",SUM);
SUM = SUM % MOD;

}
printf("%lld\n",SUM);
return 0;
}

Measured memory_bytes: 33224
use proconio::input;
use std::cmp::min;

fn main() {
    input! {
        n: usize,
        k: usize,
        height: [usize; n],
    }
    let mut res: usize = 1_000_000_000_000;

    for bit in 0..1 << n {
        let mut col: usize = 0;
        let mut budget: usize = 0;
        let mut now_h: usize = 0;
        for i in 0..n {
            if now_h < height[i] {
                now_h = height[i];
                col += 1;
            } else if bit & (1 << i) > 0 {
                now_h += 1;
                budget += now_h - height[i];
                col += 1;
            }
        }
        if col >= k {
            res = min(res, budget);
        }
    }

    println!("{}", res);
}


Measured memory_bytes: 2168
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <bitset>
#include <deque>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <iterator>
#include <string>
#include <chrono>
#include <random>
#include <tuple>
#include <utility>
#include <fstream>
#include <complex>

const long INF = (1l << 30);
const long LINF = (1l << 60);

long n;
long p[12];

int main(){
    scanf("%ld", &n);
    for(int i = 0; i < n; i++){
        scanf("%ld", p+i);
    }
    std::sort(p, p+n);
    long ans = 0;
    ans += p[n-1]/2;
    for(int i = 0; i < n-1; i++){
        ans += p[i];
    }
    printf("%ld\n", ans);
}


Measured memory_bytes: 256
/*
	*#*#*#* Author GaryMr *#*#*#*
	字符串问题是否可以用数学模拟递归过程（取c[i]或不取来算结果）
	二分？左闭右开？
	long long？
	逆向思维？
	dp？
	贪心？
	匹配括号 左减右>=0
	多组数据清空？
	dp优化用g？
	线段树：左闭右开！
	线段树：find： if(l>=b||r<=a) return 0x3f3f3f3f; if(r<=b&&l>=a) return tree[k];
	线段树：满二叉树 
	循环跳出条件 
	代数设出每个值寻找关系？
	优先队列：priority_queue<类型> q;   
	priority_queue<类,vector<类>, less<类> > pq1; 　　　 // 使用递减	
	priority_queue<类，vector<类>, greater<类> > pq2; 　　// 使用递增
	判断括号，判断是否长度为偶数
*/
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;a++)
#define rl(a,b,c) for(int a=b;a>=c;a--)
#define niv vector<int>
#define IT iterator
#define FIR first
#define SEC second
using namespace std;
const int MAX=0x3f3f3f3f;
const int MOD=1e9+7;
typedef pair<int,int> mp;
typedef pair<mp,mp> superpair;
map<int,int> m; 
long long result=1;
int n;
int main(){
	scanf("%d",&n);
	rb(i,1,n){
		char c;
		cin>>c;
		m[c-'a'+1]++;
	}
	rb(i,1,26){
		m[i]++;
		result*=m[i];
		result%=MOD;
	}
	result--;
	if(result<0) result+=MOD;
	printf("%I64d\n",result);
	return 0;
}

Measured memory_bytes: 256
h, w = map(int,input().split())
s = [input() for _ in range(h)]

g = [[]*w for _ in range(h)]

for i in range(h):
    for j in range(w):
        c = 0
        if s[i][j] == '#':
            g[i].append('#')
            continue
        for n, m in ([-1,1],[-1,0],[-1,-1],[0,1],[0,-1],[1,1],[1,0],[1,-1]):
            new_h, new_w = i + n, j + m
            if new_h < 0 or new_h >= h or new_w < 0 or new_w >= w:
                continue
            if s[new_h][new_w] == '#':
                c += 1
        g[i].append(str(c))

ans = ''
for i in range(h):
    c = ''.join(g[i])
    ans += c
    if i != h-1:
        ans += '\n'

print(ans)

Measured memory_bytes: 3188
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <algorithm>
#include <functional>
#include <cstring>
#include <string>
#include <sstream>
#include <bitset>
using namespace std;
#define INF	100000000
#define MOD 1000000007
#define pb push_back
#define mp make_pair
#define fi first
#define sec second
#define lb lower_bound
#define ub upper_bound
#define SS stringstream
#define rep(i,n) for(int i = 0; i < n; i++)
#define SORT(x) sort((x).begin(), (x).end())
#define clr(a,b) memset((a),(b),sizeof(a))
typedef long long int ll;
typedef pair<double, string> P;
typedef vector<int> Vi;
typedef vector<ll> Vll;
typedef vector<P> Vp;
typedef priority_queue<P, vector<P>, greater<P> > PQ;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	while(cin >> n,n){
		Vp vec;
		rep(i,n){
			string l;
			int p,a,b,c,d,e,f,s,m;
			cin >> l >> p >> a >> b >> c >> d >> e >> f >> s >> m;
			int t = a+b+c,money = f*s*m-p;
			rep(j,m) t += d+e;
			vec.pb(P(-1.0*(double)money/(double)t,l));
		}
		sort(vec.begin(),vec.end());
		rep(i,n){
			cout << vec[i].sec << endl;
		}
		cout << "#" << endl;
	}
}

Measured memory_bytes: 1224
package main

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

var sc = bufio.NewScanner(os.Stdin)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, _ := strconv.Atoi(sc.Text())
	return i
}

func nextFloat64() float64 {
	f, _ := strconv.ParseFloat(next(), 64)
	return f
}

func nextInts(n int) []int {
	slice := make([]int, n)
	for i := 0; i < n; i++ {
		slice[i] = nextInt()
	}
	return slice
}

func main() {
	sc.Split(bufio.ScanWords)
	fmt.Println(24 + 24 - nextInt())
}


Measured memory_bytes: 640
#include <iostream>

using namespace std;


int main(){

	int n;
	int k[100];
	char data[53] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";

	string s;

	/*
	cout<<"A"<<(int)'A'<<endl;
	cout<<"Z"<<(int)'Z'<<endl;
	cout<<"a"<<(int)'a'<<endl;
	*/

	while(cin>>n){
		if(n==0)break;
		for(int i=0;i<n;i++){
			cin>>k[i];
		}
		cin>>s;

		for(int i=0;i<s.size();i++){
			
			int num = s.at(i)-'A';
			if(s.at(i)>='a'){
				num -=6;
			}

			num -=k[i%n];

			if(num<0) num+=52;
			else if(num>52) num-=52;

			cout<<data[num];
		}

		cout<<endl;
	}

	return 0;
}

Measured memory_bytes: 1196
import std.stdio, std.conv, std.string, std.array, std.range, std.algorithm, std.container;
import std.math, std.random, std.bigint, std.datetime, std.format;
void main(string[] args){ if(args.length > 1) if(args[1] == "-debug") DEBUG = 1; solve(); }
void log()(){ writeln(""); } void log(T, A ...)(T t, lazy A a){ if(DEBUG) write(t, " "), log(a); } bool DEBUG = 0; 
string rstring(){ static string[] ss; while(!ss.length) ss = readln.chomp.split; string res = ss[0]; ss.popFront; return res; }
T rtype(T)(){ return rstring.to!T; } alias rint = rtype!int, rlong = rtype!long, rreal = rtype!real;
T[] rtypes(T)(int n){ return n.iota.map!(i => rtype!T()).array; } alias rint = rtypes!int, rlong = rtypes!long, rreal = rtypes!real;
T[][] rtypess(T)(int n, int m){ return n.iota.map!(i => rtypes!T(m)).array; } alias rint = rtypess!int, rlong = rtypess!long, rreal = rtypess!real;

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

void solve(){
	int n = rint;
	int[] as = rint(n);
	
	int[int] ac;
	foreach(a; as){
		if(a !in ac) ac[a] = 0;
		ac[a] += 1;
	}
	
	int xlim;
	int[] us = new int[](n + 1);
	int[] aks = ac.keys;
	foreach(ak; aks){
		foreach(x; 0 .. ac[ak]) us[x] += ac[ak] - x;
		xlim = max(xlim, ac[ak]);
	}
	
	
	int ans = n;
	foreach(k; 1 .. n + 1){
		while(k * ans > n - us[ans]) ans -= 1;
		ans.writeln;
	}
	
}
/*
「x回操作を行えるような最大のKは？」を考える。

x回操作を行うということは、同じ数字は高々x枚しか出せない。
その制限により出せなくなるカードを除き、出せるカードを全部持ってくる。

それがm枚であったとする。
Kはm/x。

xを増やすと、出せるカードは増えるが、
x→x'としてもmはどんなに多く増えても x' / x 倍まで。
よってKはxを増やすと単調増加。
*/

/*
x回操作を行うときに出せないカードの枚数 us[x]

*/


Measured memory_bytes: 27848
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;


public class Main {

	public static void main(String[] args) throws IOException {
		ContestScanner scan = new ContestScanner();

		(new Solve(scan.nextInt(), scan.nextInt())).solve();
	}
}
class Solve {
	private final int x;
	private final int y;

	public Solve(final int x, final int y)
	{
		this.x = x;
		this.y = y;
	}

	public void solve()
	{
		System.out.println(gcd(x,y));
	}

	public int gcd(final int a, final int b)
	{
		if(b == 0) return a;
		else return gcd(b, a % b);
	}
}
class ContestScanner {
	BufferedReader reader;
	String[] line;
	int index;
	public ContestScanner() {
		reader = new BufferedReader(new InputStreamReader(System.in));
	}

	public ContestScanner(String filename) throws FileNotFoundException {
		reader = new BufferedReader(new InputStreamReader(new FileInputStream(filename)));
	}

	public String nextToken() throws IOException {
		if(line == null || index >= line.length)
		{
			line = reader.readLine().trim().split(" ");
			index = 0;
		}

		return line[index++];
	}

	public String next() throws IOException {
		return nextToken();
	}

	public String readLine() throws IOException {
		line = null;
		index = 0;

		return reader.readLine();
	}

	public int nextInt() throws IOException, NumberFormatException {
		return Integer.parseInt(nextToken());
	}

	public long nextLong() throws IOException, NumberFormatException {
		return Long.parseLong(nextToken());
	}

	public double nextDouble() throws IOException, NumberFormatException {
		return Double.parseDouble(nextToken());
	}

	public int[] nextIntArray(int N) throws IOException, NumberFormatException {
		int[] result = new int[N];

		for(int i=0; i < N; i++) result[i] = nextInt();

		return result;
	}

	public long[] nextLongArray(int N) throws IOException, NumberFormatException {
		long[] result = new long[N];

		for(int i=0; i < N; i++) result[i] = nextLong();

		return result;
	}

	public double[] nexDoubleArray(int N) throws IOException, NumberFormatException {
		double[] result = new double[N];

		for(int i=0; i < N; i++) result[i] = nextDouble();

		return result;
	}
}

Measured memory_bytes: 24436
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::*;
use std::collections::*;
use std::io::Write;

#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), std::io::stderr());
            writeln!(err, "{} = {:?}", e, $e).unwrap()
        })*
    };
}

fn main() {
    let v = read_vec::<i64>();
    let (n, t) = (v[0] as usize, v[1]);
    let h = read_vec::<i64>();
    let mut ans = t;
    for i in (0..n - 1).rev() {
        ans += min(t, h[i + 1] - h[i]);
    }
    println!("{}", ans);
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}


Measured memory_bytes: 8444
input_a = int(input())
input_b = int(input())

if (input_a == 1):
    if(input_b == 2):
        print(3)
    else:
        print(2)
elif (input_a == 2):
    if(input_b == 1):
        print(3)
    else:
        print(1)
else:
    if(input_b == 1):
        print(2)
    else:
        print(1)


Measured memory_bytes: 3060
n = int(input())
l = [list(map(int, input().split())) for i in range(n)]

a = sorted(l, key=lambda x:x[0])
b = sorted(l, key=lambda x:x[1])

if n % 2 == 1:
  print(b[n//2][1] - a[n//2][0] +1)
else:
  print((b[n//2][1]+b[n//2-1][1])-(a[n//2][0]+a[n//2-1][0])+1)


Measured memory_bytes: 51768
<?php
while(1) {
    list($h, $w) = explode(" ", fgets(STDIN));
    if($h==0 && $w==0) break;
    $o = str_repeat("#", (int)$w);
    $u = "#" . str_repeat(".", (int)($w)-2) . "#";
    echo($o . "\n");
    for($y=2; $y<$h; $y++) {
        echo($u . "\n");
    }
    echo($o . "\n");
    echo("\n");
}



Measured memory_bytes: 9228
#include"bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
using namespace std;

int main() {
	string s;
	cin >> s;
	int num = 8;
	while (num--) {
		s.pop_back();
	}
	cout << s << endl;
	return 0;
}


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

#define fr(i,n) _back
#define pb	push_back
#define eb	emplace_back
#define mk	make_pair
#define fi	first
#define se	second
#define endl	'\n'

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<ii> vii;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
const int T = 1e5 + 3;
int h[T];
vector<int> g[T];

int main() {
    ios_base::sync_with_stdio(false);
    int n,m;
    cin >> n >> m;
    for(int i = 1; i <=n;i++) cin >> h[i];

    while(m--) {
        int x,y; cin >> x >> y;
        g[x].pb(y);
        g[y].pb(x);
    }

    int ans = 0;
    for(int i = 1; i <= n; i++) {
        bool ok = 1;
        for(int v : g[i]) ok &= (h[i]>h[v]);
        ans += ok;
    }

    cout << ans << endl;

    return 0;
}



Measured memory_bytes: 9052
#include <iostream>
#include <stdio.h>
#include <fstream>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <limits.h>
#include <math.h>
#include <functional>
#include <bitset>

#define repeat(i,n) for (long long i = 0; (i) < (n); ++ (i))
#define debug(x) cerr << #x << ": " << x << '\n'
#define debugArray(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i] << '\n'
#define debugArrayP(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i].first<< " " << x[i].second << '\n'

using namespace std;

typedef long long ll;
typedef pair<int,int> Pii;
typedef vector<int> vint;
typedef vector<ll> vll;
const ll INF = LLONG_MAX/10;
const ll MOD = 1e9+7;

int main(){
  string s;cin>>s;
  int cnt[3]={0,0,0};
  repeat(i,s.length()){
    cnt[s[i]-'a']++;
  }
  cout << (max({cnt[0],cnt[1],cnt[2]})-min({cnt[0],cnt[1],cnt[2]})<=1? "YES":"NO")<<endl;
}


Measured memory_bytes: 512
MOD=10**9+7
N=int(input())
xlist=list(map(int,input().split()))

fact_nm1=1
for i in range(1,N):
  fact_nm1*=i
  fact_nm1%=MOD
#print(fact_nm1)

answer_bunshi=0
answer_bumbo=1
inv_bunshi=0
inv_bumbo=1
for i in range(1,N):  
  inv_bunshi=(i*inv_bunshi+inv_bumbo)%MOD
  inv_bumbo=(inv_bumbo*i)%MOD
  #print(inv_bunshi,inv_bumbo)
  
  xdiff=xlist[i]-xlist[i-1]
  term_bunshi=(xdiff*inv_bunshi)%MOD
  answer_bunshi=(answer_bunshi*inv_bumbo+term_bunshi*answer_bumbo)%MOD
  answer_bumbo=(answer_bumbo*inv_bumbo)%MOD
#print(answer_bunshi,answer_bumbo)

answer_bunshi=(answer_bunshi*fact_nm1)%MOD
answer=answer_bunshi*pow(answer_bumbo,MOD-2,MOD)
answer%=MOD
print(answer)

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

const ll MAXN = 200000;

ll N, ans=0, tmp=0;
vector<ll> A, B;

signed main(){
    cin >> N;
    for(int i=0;i<N;i++) {
        ll a, b;
        cin >> a >> b;
        ans -= b;
        A.push_back(a+b);
    }
    sort(A.begin(), A.end());
    for(int i=A.size()-1;i>=0;i-=2) {
        ans += A[i];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1400
import sys
import itertools


class Team:
    def __init__(self, number, score):
        self.number = number
        self.score = score


class RankChecker:
    def __init__(self):
        self.teams = []

    def add(self, team):
        self.teams.append(team)

    def aggregate(self):
        self.teams.sort(key=lambda t: t.score, reverse=True)
        r = 0
        for k, g in itertools.groupby(self.teams, key=lambda t: t.score):
            r += 1
            for t in g:
                t.rank = r

    def check_rank(self, team_number):
        team = filter(lambda t: t.number == team_number, self.teams)[0]
        return team.rank



rc = RankChecker()
for line in sys.stdin:
    num, score = map(int, line.strip().split(','))
    if (num, score) == (0, 0):
        break
    rc.add(Team(num, score))
rc.aggregate()
for line in sys.stdin:
    num = int(line)
    print rc.check_rank(num)

Measured memory_bytes: 4392
#include <stdio.h>

typedef long long ll;

int main(void) {
  
  int n, m;
  scanf("%d %d", &n, &m);
  ll H[n+1];
  int data[n+1];
  for(int i = 1;i <= n;i++) {
    scanf("%lld", H + i);
    data[i] = 0;
  }
  for(int i = 0;i < m;i++) {
    int a, b;
    scanf("%d %d", &a, &b);
    int c = H[a] - H[b] > 0 ? b : a;
    data[c]++;
    if(H[a] == H[b]) data[c == a ? b : a]++;
  }
  int ret = 0;
  for(int i = 1;i <= n;i++) {
    if(data[i] == 0) ret++;
  }
  printf("%d\n", ret);
  
  return 0;
}

Measured memory_bytes: 3316
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.TreeMap;

public class Main {
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String str[] = br.readLine().split(" ");

		long n = Long.parseLong(str[0]);
		long k = Long.parseLong(str[1]);

		long cnt[] = new long[100001];

		for (long i = 0; i < n; i++) {
			str = br.readLine().split(" ");

			long a = Long.parseLong(str[0]);
			long b = Long.parseLong(str[1]);

			cnt[(int) a] += b;
		}

		long count = 0;
		for (int i = 0; i < cnt.length; i++) {
			count += cnt[i];
			if (count >= k) {
				System.out.println(i);
				return;
			}
		}
	}

}


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

using namespace std;
#define int            long long
#define f(i,n)        for(int i=0;i<(n);++i)
#define fa(i,a,n)     for(int i=a;i<=(n);++i)
#define fd(i,a,n)     for(int i=a;i>=(n);--i)
#define tc 			  int t;cin>>t;f(testcase,t)
#define pii             pair<int,int>
void c_p_c() {

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

}

int32_t main() {

	c_p_c();
	int n, k, x, y;
	cin >> n >> k >> x >> y;
	int ans = 0;

	ans += (x * min(n, k));
	n -= k;
	if (n > 0)
		ans += (y * n);
	cout << ans;


	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define MIN(a,b) ((a) <= (b) ? (a) : (b))
#define ALL(v) (v).begin(), (v).end()
#define SORT(v) sort( ALL(v) )

using namespace std;
using ll = long long;
using P = pair<int,int>;


int main()
{

    int X,Y;
    cin>>X>>Y;

    int A,B,C;
    cin>>A>>B>>C;

    vector<int> arr1(A);
    vector<int> arr2(B);
    vector<int> arr3(C);
    vector<int> OUT;




    rep(i,A)cin>>arr1[i];
    rep(i,B)cin>>arr2[i];
    rep(i,C)cin>>arr3[i];
    sort(arr1.rbegin() , arr1.rend());
    sort(arr2.rbegin() , arr2.rend());
    sort(arr3.rbegin() , arr3.rend());

    rep(i,X)OUT.push_back(arr1[i]);     rep(i,Y)OUT.push_back(arr2[i]);     rep(i,C)OUT.push_back(arr3[i]);

    sort(OUT.rbegin() , OUT.rend());
    ll ans = 0 ;
    rep(i , X+Y)ans+=OUT[i];



    cout << ans << endl;



    return 0;
}


Measured memory_bytes: 3572
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  vector<double> a(n);
  double sum=0;
  for(int i=0;i<n;i++){
    cin >> a[i];
    sum+=1/a[i];
  }
  cout << fixed << setprecision(10) << 1/sum << endl;
}

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

using namespace std;

#define fastio cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(0)
typedef long long ll;
//#define int ll
#define swap(x, y)((x)^=(y)^=(x)^=(y))
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vector<int>> matrix;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define all(c) c.begin(),c.end()
#define mp make_pair
#define pb push_back
#define f first
#define tcase int _; cin>> _; for( ; _; --_)
#define s second
#define endl '\n'
const int MAX = 1e6+1;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1);
const double DEG = 180/PI;
const int MOD = 1e9+7;
int mod(int x, int m){ if(x >= 0) return x % m; if(-x < m) return m-(-x); return mod(x%m, m);}
int gcd (int a, int b) {while(b){a = mod(a, b); swap(a, b);} return a;}
int lcm (int a, int b) {return a / gcd(a, b) * b;}
int fexp(int base, int exp, int m){
	int total = 1;
	while(exp > 0){
		if(exp % 2 == 1){
			total = mod(((mod(total, m)) * (mod(base, m))), m);
			exp--;
		}
		base= mod((mod(base, m) * mod(base, m)), m);
		exp /= 2;
	}
	return mod(total, m);
}

int n;

void solve(){
	cin>> n;
	vi a(n), b(n), c(n);

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

	int dp[n+1][3];
	memset(dp, 0, sizeof(dp));
	dp[0][0] = a[0];
	dp[0][1] = b[0];
	dp[0][2] = c[0];

	for(int i = 1; i<n; ++i){
		for(int j = 0; j<3; ++j){
			for(int k = 0; k<3; ++k){
				if(j == k) continue;

				if(j == 0) dp[i][j] = max(dp[i][j], dp[i-1][k] + a[i]);
				else if(j == 1) dp[i][j] = max(dp[i][j], dp[i-1][k] + b[i]);
				else dp[i][j] = max(dp[i][j], dp[i-1][k] + c[i]);
			}
		}
	}
	cout<< max(dp[n-1][0], max(dp[n-1][1], dp[n-1][2])) << endl;
}

int32_t main(){
	fastio;
	solve();
	return 0;
}


Measured memory_bytes: 5560
#define _USE_MATH_DEFINES
#include<iostream>
#include<algorithm>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<deque>
#include<map>
#include<set>
#define ll long long
#define dou(s) atof(s.c_str())
#define lon(s) atoll(s.c_str())
#define str(n) to_string(n)
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define rrep(i,b,a) for(ll i=b;i>=a;i--)
#define ALL(a) a.begin(),a.end()
#define fion(n) fixed<<setprecision(n)
#define endl "\n"
#define OR ||
#define AND &&
#define NOT !
#define line(s) getline(cin,s)
#define fdarst(a,n) (a[a.size()-1]>=n&&a[lower_bound(ALL(a),n)-a.begin()]==n?lower_bound(ALL(a),n)-a.begin():-1)
#define fist(s,t) ((int)s.find(t))
#define START int main(){cin.tie(0);ios::sync_with_stdio(false);
#define END }
using namespace std;
bool f(const vector<ll> &a, ll k, ll i = 0) {
	if (k == 0)return true;
	if (k < 0 OR i == a.size())return false;
	return f(a, k, i + 1) OR f(a, k - a[i], i + 1);
}
START
ll n; cin >> n;
vector<ll> a(n);
rep(i, 0, n)cin >> a[i];
ll m, q; cin >> m;
rep(i, 0, m) {
	cin >> q;
	cout << (f(a, q) ? "yes" : "no") << endl;
}
END


Measured memory_bytes: 3164
Line = [int(s) for s in input().split()]
n,M,X = Line[0],Line[1],Line[2]

ans = -1
money = []

item = [0]*n
# print(item)
# print(X)


for i in range(n):
    item[i] = [int(s) for s in input().split()]
# print(item)

for i in range(2 ** n):
    bag = []
    algos = [0]*M
    # print("pattern {}: ".format(i), end="")
    total = 0
    for j in range(n):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            bag.append(item[j][0])  # フラグが立っていたら bag に果物を詰める
            total += item[j][0]  # 買い物累計額にも加算
            for x in range(M):
                algos[x] += item[j][x+1]
    # print(algos)
            
    if (all(elem >= X for elem in algos)):
        # print(total, bag,algos)
        ans = 1
        money.append(total)
if ans == 1:
    print(min(money))
else:
    print(-1)

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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;

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

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
template <class T, class Y>T GCD(T a, Y b){if(a<b){int c=a;a=b;b=c;}if (a % b == 0){return b;}return GCD(b, a % b);}
template<class T,class Y>T LCM(T a,Y b){return (a*b)/GCD(a,b);}
void clear(queue<pair<int, int>> &q){queue<pair<int, int>> empty;swap(q, empty);} //queueの中身の型は適時変更を忘れない

using vi=vector<int>;
using vii=vector<vi>;

#define REP(i,a,b) for(ll i=(a);i<(b);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define rv reverse
#define ALL(a) (a).begin(),(a).end()
#define decimal(x) fixed<<setprecision(x)

int main(){
    ll n,p,ans=1;
    cin>>n>>p;
    map<ll,ll>mp;
    for(ll i=2;i<=sqrt(p);){
        if(p%i==0){
            p/=i;
            mp[i]++;
        }else i++;
        //cout<<i<<endl;
    }
    if(p!=1)mp[p]++;
    //最大公約数の最大化なので、数列全体に数を割り当てられるだけ割り当てなければいけない。
    //n個以上の時、一回だけとしてしまったので、2*n以上あったときに割り当てられるのに割り当てられなくなってしまいWA
    for(auto x:mp){
        //cout<<x.first<<":"<<x.second<<endl;
        rep(i,x.second/n){
            ans*=x.first;
        }
    }
    cout<<ans<<endl;
    return 0;
}

//a=97,z=122

Measured memory_bytes: 3668
/*
  || Shree Ganeshay Namah ||

     || Jai Shree Ram ||
  || Nabh Sparsham Diptam ||
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;

#define mod 1000000007
#define block 180
#define ff first.first
#define fs first.second
#define sf second.first
#define ss second.second
#define f1 first
#define s1 second
#define pb push_back
// to floor a/b you can do a/b and to ceiling a/b you can do (a+b-1)/b
int jai_shree_ram()
{
    return 1;
}
int shree_ganeshay_namah()
{
    return 1;
}
ll power(ll x,ll y)
{
    ll r=1;
    while(y>0)
    {
        if(y%2!=0)
            r=(r* x);
        x=(x* x);
        y=y/2;
    }
    return r;
}
ll ncr(ll n,ll k)
{

    ll c[k+1];
    memset(c,0,sizeof(c));
    c[0]=1;
    for(ll i=1;i<=n;i++)
    {
        for(ll j=min(i,k);j>0;j--)
            c[j]=(c[j]%mod + c[j-1]%mod)%mod;
    }
    return c[k];
}

bool prime[1001];
void sieve()
{
    ll i,j;
    memset(prime,true,sizeof(prime));
    prime[0]=false;
    prime[1]=false;
    for(i=2;i<=sqrt(100);i++)
    {
        if(prime[i])
        {
            for(j=i*i;j<=100;j=j+i)
                prime[j]=false;
        }
    }
}
//Start of Matrix Exponentiation Code
void mat_mul(ll F[2][2],ll M[2][2]) {
   ll a = ((F[0][0]%mod * M[0][0]%mod)%mod + (F[0][1]%mod * M[1][0]%mod)%mod)%mod;
   ll b = ((F[0][0]%mod * M[0][1]%mod)%mod + (F[0][1]%mod * M[1][1]%mod)%mod)%mod;
   ll c = ((F[1][0]%mod * M[0][0]%mod)%mod + (F[1][1]%mod * M[1][0]%mod)%mod)%mod;
   ll d = ((F[1][0]%mod * M[0][1]%mod)%mod + (F[1][1]%mod * M[1][1]%mod)%mod)%mod;
   F[0][0] = a;
   F[0][1] = b;
   F[1][0] = c;
   F[1][1] = d;
}
void mpower(ll F[2][2], ll n) {
   if (n == 0 || n == 1)
      return;
   ll M[2][2] = {{1,1},{1,0}};
   mpower(F, n / 2);
   mat_mul(F, F);
   if (n % 2 != 0)
      mat_mul(F, M);
}
ll fib_mat(ll n) {
   ll F[2][2] = {{1,1},{1,0}};
   if (n == 0)
      return 0;
   mpower(F, n - 1);
   return F[0][0]%mod;
}
//End of Matrix Exponentiation
/*
Segment Tree
ll ar[200005];
ll st[800005];
void build(ll si,ll ss,ll se)
{
    if(ss==se)
    {
        st[si]=ar[ss];
        return ;
    }
    ll mid=(ss+se)/2;
    build(2*si,ss,mid);
    build(2*si+1,mid+1,se);
    st[si]=(st[2*si]+st[2*si+1]);
}
ll query(ll si,ll ss,ll se,ll l,ll r)
{

   if(l<=ss && se<=r)
     return st[si];
   if(l>se || r<ss)
    return 0;
   ll mid=(ss+se)/2;
   ll x=query(2*si,ss,mid,l,r);
   ll y=query(2*si+1,mid+1,se,l,r);
   return x+y;
}
void update(ll si,ll ss,ll se,ll qi)
{
    if(ss==se)
    {
        st[si]=ar[ss];
        return;
    }
    ll mid=(ss+se)/2;
    if(qi<=mid)
        update(2*si,ss,mid,qi);
    else
        update(2*si+1,mid+1,se,qi);
    st[si]=st[2*si]+st[2*si+1];
}
*/

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll n,W,i,j;
	cin>>n>>W;
	ll w[n],v[n];
	for(i=0;i<n;i++)
        cin>>w[i]>>v[i];
    ll dp[n+1][W+1];
    memset(dp,0,sizeof(dp));
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=W;j++)
        {
            dp[i][j]=dp[i-1][j];
            if(j>=w[i-1])
                dp[i][j]=max(dp[i][j],v[i-1]+dp[i-1][j-w[i-1]]);
        }
    }
    cout<<dp[n][W];
	return 0;
}


Measured memory_bytes: 82480
N = int(input())
D = list(map(int, input().split()))
D = sorted(D)

if N == 1:
    print(D[0])
    exit()

time = [0]
for i in range(N):
    max_24 = 24
    max_0 = 24
    for j in range(len(time)):
        max_0 = min(abs(time[j] - D[i]), max_0)
        max_24 = min(abs(time[j] - (24-D[i])), max_24)
    if max_0 >= max_24:
        time.append(D[i])
    else:
        time.append(24 - D[i])

time.append(24)
ans = 12
for i in range(len(time)):
    for j in range(i+1, len(time)):
        ans = min(ans, abs(time[i] - time[j]))

print(ans)

Measured memory_bytes: 9180
import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
	Scanner scan = new Scanner(System.in);
	while(scan.hasNext()) {
	    String input = scan.nextLine();
	    String[] inputs = input.split(" ");
	    int x = Integer.parseInt(inputs[0]);
	    int y = Integer.parseInt(inputs[1]);
	    if (x == 0 && y == 0) {
		break;
	    }
	    if (x < y) {
		System.out.println(x + " " + y);
	    } else {
		System.out.println(y + " " + x);
	    }
	}
    }
}

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

using namespace std;

int main(){
  string s;
  cin >> s;
  int n = (int)s.size() + 1;
  
  vector<int> a(n, -1);
  if(s[0] == '<') a[0] = 0;
  for(int i = 1; i < n - 1; i++){
    if(s[i - 1] != s[i]){
      if(s[i - 1] == '>') a[i] = 0;
      else a[i] = -2;
    }
  }
  if(s[n - 2] == '>') a[n - 1] = 0;
  
  for(int i = 0; i < n - 1; i++){
    if(s[i] == '<' && a[i] == -1) a[i] = a[i - 1] + 1;
  }
  if(s[n - 2] == '<') a[n - 1] = a[n - 2] + 1;
  
  for(int i = n - 2; i >= 0; i--){
    if(s[i] == '>' && a[i] == -1) a[i] = a[i + 1] + 1;
  }
  if(s[0] == '>') a[0] = a[1] + 1;
  
  for(int i = 0; i < n; i++){
    if(a[i] == -2) a[i] = max(a[i - 1], a[i + 1]) + 1;
  }
  
  long long sum = 0;
  for(int i = 0; i < n; i++){
    sum += (long long)a[i];
  }
  
  cout << sum << endl;
}

Measured memory_bytes: 2820
#include <stdio.h>
int main(){
  int a,b,c,p;
  scanf("%d %d %d",&a,&b,&c);
  if(b<a){
    p=b,b=a,a=p;
  } if(c<b){
    p=c,c=b,b=p;
  } if(b<a){
    p=b,b=a,a=p;
  }
  printf("%d %d %d\n",a,b,c);
  return 0;
}

Measured memory_bytes: 2664