akhauriyash/Code-Regression huggingface dataset:
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    ArrayList<Pair> list1 = new ArrayList<>(n);
    ArrayList<Pair> list2 = new ArrayList<>(n);
    Map<Pair, Integer> map = new HashMap<>();
    for (int i = 0; i < n; i++) {
      int a = sc.nextInt();
      int b = sc.nextInt();
      Pair p = new Pair(a, b);
      list1.add(p);
      list2.add(p);
      int current = map.getOrDefault(p, 0);
      map.put(p, current + 1);
    }
    list1.sort((o1, o2) -> o2.c - o1.c);
    list2.sort((o1, o2) -> o2.c - o1.c);
    int list1Cursor = 0;
    int list2Cursor = 0;
    long total1 = 0;
    long total2 = 0;
    boolean isTurnList1 = true;
    for (int i = 0; i < n; i++) {
      if (isTurnList1) {
        for (;;) {
          Pair pair = list1.get(list1Cursor);
          list1Cursor += 1;
          int current = map.get(pair);
          if (current <= 0) continue;
          map.put(pair, current - 1);
          total1 += (long) pair.a;
          break;
        }
      } else {
        for (;;) {
          Pair pair = list2.get(list2Cursor);
          list2Cursor += 1;
          int current = map.get(pair);
          if (current <= 0) continue;
          map.put(pair, current - 1);
          total2 += (long) pair.b;
          break;
        }
      }
      isTurnList1 = !isTurnList1;
    }
    System.out.println(total1 - total2);
  }

  private static class Pair {
    private final int a;
    private final int b;
    private final int c;
    private final int e;

    private Pair(int a, int b) {
      this.a = a;
      this.b = b;
      this.c = a + b;
      this.e = Math.max(a, b);
    }

    @Override
    public boolean equals(Object o) {
      if (this == o) return true;
      if (o == null || getClass() != o.getClass()) return false;
      Pair pair = (Pair) o;
      return a == pair.a &&
              b == pair.b;
    }

    @Override
    public int hashCode() {
      return Objects.hash(a, b);
    }
  }
}

Measured memory_bytes: 101148
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <math.h>
#include <utility>
#include <algorithm>
#include <functional>
#include <vector>
#include <numeric>
#include <bits/stdc++.h>

#define int long long

struct edge {
    int to;
    int cost;
};

using namespace std;
using vi = vector<int>;
using vii = vector<vector<int>>;
using vb = vector<bool>;
using qi = queue<int>;
using P = pair<int, int>;
using graph = vector<vector<edge>>;
// using graph = vector<vector<int>>;

#define FOR(i, a, b) for (int i = a; i < (b); i++)
#define REP(i,n) for(int i=0;i<n;i++)
#define delim(i, n) cout << (i == n-1 ? "\n" : " ");

const int inf = 1LL << 60;
// const int inf = 100000000;
const int mod = 1000000007;

const int maxn = 1e6;
int n, m;
vi fact(maxn), finv(maxn), inv(maxn);

void COMinit() {
    fact.assign(2, 1);
    finv.assign(2, 1);
    inv.assign(2, 1);
    FOR(i, 2, maxn) {
        fact[i] = (fact[i-1] * i) % mod;
        inv[i] = mod - (inv[mod%i] * (mod/i)) % mod;
        finv[i] = (finv[i-1] * inv[i]) % mod;
    }
}

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

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

    // https://atcoder.jp/contests/abc034/tasks/abc034_c
    cin >> n >> m;
    if (n > m) swap(n, m);

    int dif = m - n;
    int com = n - dif;
    if (com % 3 != 0) {
        cout << 0 << "\n";
    } else {
        COMinit();
        com /= 3;
        cout << COM(2*com + dif, com) << "\n";
    }

}

Measured memory_bytes: 26580
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <list>
#include <iterator>
#include <cmath>
#include <cstdio>

using namespace std;

const long long MAX = 1e9;

int main() {
	long long s; cin >> s;
	long long x = (MAX - s % MAX) % MAX; //abs(MAX*y-x*1)==s となればよい,
	long long y = (s + x) / MAX;
	cout << "0 0 " << MAX << " 1 " << x << " " << y << endl;

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,a,b;
	cin>>n>>a>>b;
	int ansa,ansb;
	ansa=min(a,b);
	if (a+b>n) ansb=a+b-n;
	else ansb=0;
	cout<<ansa<<" "<<ansb;
	return 0;
} 

Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		if(N == 2) System.out.println(N);
		else {
			System.out.println(prime(N));
		}
		
	}
	public static int prime(int n) {
		boolean check = false;
		int count = 0;
		int ans = 0;
		int j = 0;
		
		while(ans == 0) {
			ans = n+j;
			for(int i = 2; i < n + j -1; i++) {
				if((n+j)%i == 0) {
					ans = 0;
					break;
				}
			}
			j++;
		}
		return ans;
	}
}

Measured memory_bytes: 23764
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vs = vector<string>;
using vll = vector<long long>;
using vvi = vector<vector<int>>;
using vvll = vector<vector<long long>>;
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 (b<a) {a=b; return 1;} return 0;}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int a, b, c;
    cin >> a >> b >> c;
    int x = 3*max({a,b,c}) - (a+b+c);
    if (x%2 == 0) {
        cout << x/2 << endl;
    } else {
        cout << (x+3)/2 << endl;
    }
}

Measured memory_bytes: 384
#include<iostream>
#include<string>
#include<sstream>
#include<vector>
#include<map>
#include<cctype>
#include<cstdlib>
using namespace std;
#define REP(i, j) for(int i = 0; i < j; i++)
#define FOR(i, j, k) for(int i = j; i < k; i++)
const int N = 120 * 60;
const int N3 = N * 3;

void disp(int n){
    stringstream ss;
    int h = n / (60 * 60);
    n -= (h * 60 * 60);
    int m = n / 60, s = (n - (m *  60));
    ss <<(h < 10? "0" : "") <<h <<":";
    ss <<(m < 10? "0" : "") <<m <<":";
    ss <<(s < 10? "0" : "") <<s;
    cout <<ss.str() <<endl;
}


int main(){
    int h, m, s;
    while(cin >>h >>m >>s && h != -1){
        int sum = s + (m * 60) + (h * 60 * 60);
        disp(N - sum);
        disp(N3 - 3 * sum);
    }
    return 0;
}

Measured memory_bytes: 1212
# include <bits/stdc++.h>
# pragma GCC optimize("Ofast")
# define pb push_back
# define ll long long
# define fi first
# define se second
# define all(vc) vc.begin(),vc.end()
# define forn(i, n) for (int i = 0; i < int(n); i++)
# define ford(i, n) for (int i = int(n) - 1; i >= 0; i--)
# define fore(i, l, r) for (int i = int(l); i < int(r); i++)
# define fors(i, s) for (int i = 0; s[i]; i++)
# define in freopen("input.txt", "r", stdin)
# define speed ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
# define time cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"
 
using namespace std;
 
const ll INF = 1e18;
const int mod = 1e9 + 7;
const int N = 2e5 + 7;

ll a, b, k; 
 
int main()
{
	speed;
	cin >> a >> b >> k;
	ll x = min( a, k );
	a -= x;
	k -= x;
	x = min( b, k );
	b -= x;
	k -= x;
	cout << a << ' ' << b;
	time;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String a = scan.next();
        String b = scan.next();
        String c = scan.next();
        String ans = a.substring(0, 1) + b.substring(0, 1) + c.substring(0, 1);
        System.out.println(ans.toUpperCase());
    }
}

Measured memory_bytes: 23636
#include <iostream>
#include <cstdlib>
#include <string>
#include <vector>

typedef long long ll;

class ManyEq {
  private:
    std::string str;
    ll dfs (int i, std::vector<int> v) {
     if ( i == str.size()-1 ) {
       ll sum = 0;
       for(int i=0; i<v.size(); i++){
         if ( i == v.size() - 1 ) {
           sum += std::atol(str.substr(v[i]).c_str());
           continue;
         }
         sum += std::atol(str.substr(v[i], v[i+1]-v[i]).c_str());
       }
       return sum;
     }

     ll rtn = 0;
     rtn += dfs(i+1, v);
     v.push_back(i+1); rtn += dfs(i+1, v);
     return rtn;
    }

  public:
    ManyEq ( std::string str_ ) : str(str_) {
    }

    void Sol(){
      std::cout << dfs( 0, {0} ) << std::endl;
    }
};

int main (void){
  std::string str; std::cin >> str;

  ManyEq x(str); x.Sol();
  return 0;
}


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

int main() {
	
	int X;
	int ans = 0;
	int flag = 0;
	scanf("%d", &X);

	for (int i = X; i < 1000000; i++) {

		if (X == 2 || X == 3 || X == 5 || X == 7) {
			ans = X;
			break;
		}

		if (i % 2 == 0) {
			continue;
		}
		else if (i % 3 == 0) {
			continue;
		}
		else if (i % 5 == 0) {
			continue;
		}
		else if (i % 7 == 0) {
			continue;
		}
		else {
			for (int j = 11; j < i; j++) {
				if (i % j == 0) {
					flag = 1;
					break;
				}
			}
			if (flag != 0) {
				flag = 0;
				continue;
			}
		}
		ans = i;
		break;
	}

	printf("%d", ans);

	return 0;
}



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

int main() {
  int N;
  cin >> N;
  vector<int> v(N);

  for (int i = 0; i < N;i++){
    cin >> v.at(i);
  }
  sort(v.begin(), v.end());
  reverse(v.begin(), v.end());

  int A = 0;
  int B = 0;
  for (int i = 0; i < N; i+=2) {
    A += v.at(i);
  }
  for (int i = 1; i < N;i+=2){
    B += v.at(i);
  }
  cout << A - B << endl;
}

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

typedef long long ll;
const ll mod=1e9+7;
const ll N=5e5+1;
const ll INF=1e10;

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	int n;
	cin>>n;
	map<string,int> cnt;
	vector<string> v={"AC","WA","TLE","RE"};
	string s;
	while(n--){
		cin>>s;
		cnt[s]++;
	}
	for(string ans:v) cout<<ans<<" x "<<cnt[ans]<<'\n';
}


Measured memory_bytes: 3652
#include <stdio.h>

void Do(int N){
  int i, s;
  int A[N], B[N], C[N-1];
  for(i = 0;i < N;i++) scanf("%d", &A[i]);
  for(i = 0;i < N;i++) scanf("%d", &B[i]);
  for(i = 0;i < N - 1;i++) scanf("%d", &C[i]);
  s = 0;
  for(i = 0;i < N;i++){
    s += B[A[i]-1];
    if(A[i+1] == A[i] + 1) s += C[A[i]-1];
  }
  printf("%d\n", s);
}

int main(void){
  int N;
  scanf("%d", &N);
  Do(N);
  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int main() {
  int64_t s = 0LL;
  int n; cin >> n;
  for (int i = 1; i <= n; i++) {
    if ((i % 3) && (i % 5)) {
      s += i;
    }
  }
  cout << s << endl;
  return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#include<queue>
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef pair<ll,ll> Pll;
typedef pair<double,double> Pdouble;

const int INF = 2000000000;
const int MOD = 1000000007;

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

  for(int answer= 1;answer <= 100000; answer++){
    double a1 = answer * 0.08;
    double b1 = answer * 0.10;
    ll a2 = (int)a1;
    ll b2 = (int)b1;
    if(a2 == a && b2 == b){
      cout << answer << endl;
      return 0;
    }
  }
  cout << -1 << endl;
  

}


Measured memory_bytes: 256
open System
let R T = stdin.ReadLine()|> T
let RS T = stdin.ReadLine().Split()|>Array.map T
let R2 T U = RS string|>fun c-> (c.[0]|>T),(c.[1]|>U)
let R3 T U V = RS string|>fun c-> (c.[0]|>T),(c.[1]|>U),(c.[2]|>V)
let R4 T U V W = RS string|>fun c-> (c.[0]|>T),(c.[1]|>U),(c.[2]|>V),(c.[3]|>W)
let R5 T U V W X = RS string|>fun c-> (c.[0]|>T),(c.[1]|>U),(c.[2]|>V),(c.[3]|>W),(c.[4]|>X)
let outl s = stdout.WriteLine(s|>string)
let outsep ls = stdout.WriteLine(String.concat " " (ls|>Array.map string))
let outsepl ls = stdout.WriteLine(String.concat "\n" (ls|>Array.map string))
let Mod = (1e9|>int64)+7L
[<EntryPoint>]
let main argv =
    R int
    |>fun c-> (c+1)/2
    |>outl
    0
    

Measured memory_bytes: 11220
#include <bits/stdc++.h>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define repeq(i,n) for(int (i)=0;(i)<=(int)(n);(i)++)
#define rep1(i,x,n) for(int (i)=(x);(i)<(int)(n);(i)++)
#define rep1eq(i,x,n) for(int (i)=(x);(i)<=(int)(n);(i)++)
#define rrep(i,x) for(int i=((int)(x)-1);i>=0;i--)
using namespace std;
using ll = long long;
using Int = long long;

const int MOD = 1000000007;
const ll INF = numeric_limits<ll>::max();
const int inf = 1e8;
typedef pair<int,int> P;
typedef std::priority_queue<int> IntPrioQueue;
typedef std::priority_queue<int, std::vector<int>, std::greater<int> > IntReversePrioQueue;

//少数点表示
//cout << std::fixed << std::setprecision(14) << 値

int main(){
    cin.tie( 0 ); ios::sync_with_stdio( false );
    int n;
    cin >> n;
    vector<int> b(n);
    rep(i,n-1) cin >> b[i];
    int ans = b[0];
    rep1(i,1,n-1){
        if(b[i]<b[i-1]){
            ans += b[i];
        }else{
            ans += b[i-1];
        }
    }
    ans += b[n-2];

    cout << ans << endl;
    return 0;

}

Measured memory_bytes: 256
n = int(input())
A = list(map(int, input().split()))

#%%
flag = None
up = False
down = False
ans = 1
base = A[0]

for i in range(1, n):
    if base < A[i]:
        up = True
        base = A[i]
    elif base > A[i]:
        down = True
    if (up == True) and (down == True):
        up = False
        down = False
        ans += 1
    base = A[i]
    
print(ans)


Measured memory_bytes: 20040
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <set>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <time.h>
#define ll long long
#define mp(a,b) make_pair(a,b)
#define si(n) scanf("%d",&n)
#define sl(n) scanf("%lld",&n)
#define ss(s) scanf("%s",&s)
#define pi(n) printf("%d\n",n)
#define pl(n) printf("%lld\n",n)
#define newline cout << endl;
using namespace std;

int main(){
  clock_t tStart = clock();
  ll n,k; sl(n); sl(k);
  ll arr[n];
  ll pos=-1;
  for(ll i=0;i<n;i++){
    sl(arr[i]);
    if(arr[i]==1) pos=i;
  }
  ll cnt = 0, ans = 0;
  for(ll j=pos-1;j>=0;j--){
    cnt+=1;
    if(cnt%(k-1)==0)
      ans++;
  }
  for(ll j=pos+1;j<n;j++){
    cnt+=1;
    if(cnt%(k-1)==0)
      ans++;
  }
  if(cnt%(k-1)!=0)
    ans++;
  pl(ans);
  //printf("Time taken: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);
  return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>
#include <algorithm>

using ll = long long;
/*int main() {
	int N, K, a[200001];
	ll Sum[200001] = { 0 };
	scanf("%d %d", &N, &K);
	for (int i = 1; i <= N; i++) {
		scanf("%d", a + i);
		Sum[i] = Sum[i - 1] + a[i];
	}

	int count = 0;
	for (int i = 1; i <= N; i++)
		for (int j = i; j <= N; j++)
			if (K <= (Sum[j] - Sum[i - 1]) / (j - i + 1))
				count++;

	printf("%d\n", count);
}*/
int main() {
	ll N, A, B, Diff, h[100002];
	scanf("%lld %lld %lld", &N, &A, &B);
	Diff = A - B;
	for (int i = 0; i < N; i++)
		scanf("%lld", h + i);

	std::sort(h, h + N);
	h[N]     = 0x7fffffffffffffffll;
	ll up = 1000000000, down = 0, center = (up + down) / 2;
	while (1 < (up - down)) {
		ll adown;
		for (adown = 0; h[adown] < (B * center); adown++);

		ll sum = 0;
		for (int i = adown; i < N; i++)
			sum += ((h[i] - B * center) + Diff - 1) / Diff;

		if (sum <= center)
			up = center;
		else
			down = center;
		center = (up + down) / 2;
	}

	printf("%d\n", up);
}

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

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s[] = br.readLine().split(" ");
		int n = Integer.parseInt(s[0]);
		int m = Integer.parseInt(s[1]);
		if(n == m ) {
			System.out.println("Yes");
		}else {
			System.out.println("No");
		}
	}

}


Measured memory_bytes: 21204
#include <iostream>

using namespace std;

int main(int argc, char **argv)
{
	int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int x = i;
        if(x%3==0){
            cout<<' '<<i;
        }
        else if(x%10==3){
            cout<<' '<<i;
        }else{
            while(x/=10){
                if(x%10==3){
                cout<<' '<<i;
                break;
                }
            }
            
        }
    }
    cout<<endl;
	return 0;
}

Measured memory_bytes: 3076
#include <iostream>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <bitset>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> P;
typedef vector<P> vpl;
#define rep(i,n) for(ll i=0; i<(n); i++)
#define REP(i,a,b) for(ll i=(a); i<(b); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const int inf = 1<<30;
const ll linf = 1LL<<62;
const int MAX = 510000;
ll dy[8] = {0,1,0,-1,1,-1,1,-1};
ll dx[8] = {1,0,-1,0,1,-1,-1,1};
const double pi = acos(-1);
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
template<typename T1,typename T2> inline void print2(T1 a, T2 b){cout << a << " " << b << endl;}
template<typename T1,typename T2,typename T3> inline void print3(T1 a, T2 b, T3 c){
	cout << a << " " << b << " " << c << endl;
}
const int mod = 998244353;

int main(){
	string s; cin >> s;
	ll n = s.size();
	ll ans = n;
	rep(i,n-1){
		if(s[i]!=s[i+1]){
			chmin(ans, max(i+1,n-i-1));
		}
	}
	cout << ans << endl;
}

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

int main() {
    
    for(int j=0;j<10;j++){
    string S;
    cin >> S;
        if(S=="-") break;
    int m;
    cin>>m;
    for(int i=0;i<m;i++){
        int n;
        cin>>n;
        S=S+S.substr(0,n);
        S.erase(0,n);
    }
    cout<<S<<endl;

}
}



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

int main()
{
	int N,M;
	int A[25][25];
	int B[25];
	int C;
	scanf("%d %d %d",&N,&M,&C);
	for(int i=0;i<M;i++)
		scanf("%d",&B[i]);
	for(int i=0;i<N;i++)
		for(int j=0;j<M;j++)
			cin >> A[i][j];
			int ans=0;
	for(int i=0;i<N;i++)
	{
	    int tmp=0;
		for(int j=0;j<M;j++)
			tmp+=A[i][j]*B[j];
		tmp+=C;
		if(tmp>0)
			ans++;
	}
    printf("%d\n",ans);
	return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
char a[1001];
int main()
{
	int m;
	scanf("%s",a);
	m=strlen(a);
	if (a[m-1]=='s') 
	 printf("%s%s",a,"es");
	else printf("%s%s",a,"s");
	return 0;
}

Measured memory_bytes: 3820
#include<iostream>
#include <iomanip>
#include<stdio.h>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include <queue>
#include <utility>
#include <map>
#include <set>
#include <deque>
#include <numeric>
using namespace std;

int main() {
    int N, X, ans = 0, min_ = 1000000;
    cin >> N >> X;
    for (int i = 0; i < N; i++) {
        int m;
        cin >> m;
        X -= m;
        ans++;
        min_ = min(min_, m);
    }
    ans += X / min_;

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
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; }

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ for(auto it : P) { s << "<" << it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ for(auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s << endl; }



int N, M, Q;
vector<long long> a, b, c, d;

long long score(const vector<int> &A) {
    long long res = 0;
    for (int i = 0; i < Q; ++i) if (A[b[i]] - A[a[i]] == c[i]) res += d[i];
    return res;
}

void dfs(vector<int> &A, long long &res) {
    if (A.size() == N) {
        chmax(res, score(A)); // スコアを計算して更新
        return;
    }
    long long ba = (A.empty() ? 0 : A.back());
    for (int add = ba; add < M; ++add) {
        A.push_back(add);
        dfs(A, res);
        A.pop_back();
    }
}

int main() {
    cin >> N >> M >> Q;
    a.resize(Q); b.resize(Q); c.resize(Q); d.resize(Q);
    for (int q = 0; q < Q; ++q) {
        cin >> a[q] >> b[q] >> c[q] >> d[q];
        --a[q], --b[q];
    }
    long long res = 0;
    vector<int> A;
    dfs(A, res);
    cout << res << endl;
}


Measured memory_bytes: 3592
#include <iostream>

using namespace std;

int main(void) {
    int64_t H;
    cin >> H;
    for(int i=0; i<60; i++) {
        if(H < (1LL<<i)) {
            cout << (1LL<<i) - 1 << endl;
            return 0;
        }
    }
}


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

#define ll long long
#define fw(p) for(int w=0;w<(p);w++)
#define fx(p) for(int x=0;x<(p);x++)
#define fy(p) for(int y=0;y<(p);y++)
#define fz(p) for(int z=0;z<(p);z++)
#define fyg(p,g) for(int y=(g);y<(p);y++)
#define fzg(p,g) for(int z=(g);z<(p);z++)
#define ce(d) cout<<d<<endl;
#define vecp(p) int aa;cin>>aa;(p).push_back(aa);
#define vecpl(p) long long aa;cin>>aa;(p).push_back(aa);
#define vecps(p) string aa;cin>>aa;(p).push_back(aa);
#define vecp2(p) cin>>aa;(p).push_back(aa);
#define vecpl2(p) long long a	b;cin>>ab;(p).push_back(ab);
#define vecps2(p) string ab;cin>>ab;(p).push_back(ab);
#define sorts(c) sort((c).begin(),(c).end());
#define reverses(c) reverse((c).begin(),(c).end());
#define vec(b) vector<int> (b);
#define vecl(b) vector<long long> (b);
#define vecs(b) vector<string> (b);
#define pb(b,a) (b).push_back((a));
#define doublece(a,b) cout<<(a)<<' '<<(b)<<endl;
#define pairs(s) vector<pair<int,int>> (s);
#define pairsp(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define MOD 1000000007
#define cey ce("Yes")
#define cen ce("No")
#define ceY ce("YES")
#define ceN ce("NO")

int main()
{
int N;
	cin >> N;
	N = 10000 - N;
	ce(N%1000)
    return 0;
}



Measured memory_bytes: 3644
#include <cstdio>

int main(){
    int a,b,c;
    scanf("%d %d %d",&a,&b,&c);
    int s[] = {a,b,c};
    int max = a;
    int others = 0;
    for(int i = 1; i < 3; i++){
        if(max <= s[i]){
            others += max;
            max = s[i];
        }
        else{
            others += s[i];
        }
    }

    if(max == others){
        printf("Yes");
    }
    else{
        printf("No");
    }
    printf("\n");

    return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000

int sum[3][4010];
int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N; cin >> N;
    string S; cin >> S;
    rep(i, N) {
        if (S[i] == 'R') sum[0][i + 1]++;
        else if (S[i] == 'G') sum[1][i + 1]++;
        else sum[2][i + 1]++;
    }
    rep(i, 3) {
        rep(j, N) {
            sum[i][j + 1] += sum[i][j];
        }
    }
    ll ans = 0;
    rep(i, N) {
        REP(j, i + 1, N - 1) {
            if (S[i] == S[j]) continue;
            if (S[i] != 'R' && S[j] != 'R') {
                ans += sum[0][N] - sum[0][j];
            } else if (S[i] != 'G' && S[j] != 'G') {
                ans += sum[1][N] - sum[1][j];
            } else {
                ans += sum[2][N] - sum[2][j];
            }
            //cout << i << " " << j << " " << ans << endl;
            int k = (j - i) + j;
            if (k >= N) continue;
            if (S[i] != S[k] && S[j] != S[k]) ans--;
            //cout << i << " " << j << " " << k << " " << ans << endl;
        }
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3668
#include<bits/stdc++.h>
using namespace std;
int main(){
    int l1,l2,r1,r2; 
    cin>>l1>>l2>>r1>>r2;
    if(l1+l2>r1+r2){
    	cout<<"Left"<<endl;
    	return 0;
	}   
	if(l1+l2==r1+r2){
		cout<<"Balanced";
		return 0;
	}
    if(l1+l2<r1+r2){
    	cout<<"Right"<<endl;
    	return 0;
	}
    return 0;
}

Measured memory_bytes: 256
import sys

n=int(sys.stdin.readline())
B=list(map(int,sys.stdin.readline().split()))
a=0
first=1
for b in B:
    if first==1:
        a=b
        pre=b
        first=0
    else:
        a+=min(b,pre)
        pre=b
        
a+=pre
print(a)


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

int n, a[505];

int main() {
	scanf("%d", &n);
	n *= 2;

	for(int i = 0; i < n; i++)
		scanf("%d", &a[i]);

	sort(a, a + n);

	int ans = 0;
	for(int i = 0; i < n; i += 2)
		ans += a[i];

	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <list>
#include<utility>
#include <new>
#include <string>
#include<cmath>
#include<unordered_set>
#include<iomanip>
#include <stack>
#include<queue>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
#define loop(i,x,z) for (int i=x;i<z;i++)
using ll =  long long int;
#define mod 1000000007
/*bool cmp(pair<ll,ll>a,pair<ll,ll>b){
return a.second<b.second;
}*/
int main()
{
    string s,t;
    cin>>s>>t;
    vector<int>lps;
    int n=s.length(),k=t.length();
    int ans=INT_MAX;
    for(int i=0;i<n-k+1;i++){
        int z=i;
        int j=0;
        int l=0;
        while(z<n&&j<k){
            if(s[z]!=t[j]){
                l++;
            }
            z++;
            j++;
        }
        ans=min(ans,l);
    }
cout<<ans;
	return 0;
}


Measured memory_bytes: 3576
import java.util.*;
import java.io.*;
import java.awt.geom.*;
import java.math.*;

public class Main {

	static final Scanner in = new Scanner(System.in);
	static final PrintWriter out = new PrintWriter(System.out,false);
	static boolean debug = false;

	static void solve() {
		int q = in.nextInt();
		StringBuilder s = new StringBuilder();
		long l = 0, r = 0;
		while (q-- > 0) {
			long pos = in.nextLong();
			char c = in.next().charAt(0);
			int n = in.nextInt();
			if (c == '(') {
				l += n;
			} else {
				r += n;
			}
			out.println(l == r ? "Yes" : "No");
		}
	}

	public static void main(String[] args) {
		debug = args.length > 0;
		long start = System.nanoTime();

		solve();
		out.flush();

		long end = System.nanoTime();
		dump((end - start) / 1000000 + " ms");
		in.close();
		out.close();
	}

	static void dump(Object... o) { if (debug) System.err.println(Arrays.deepToString(o)); }
}

Measured memory_bytes: 54432
#include <bits/stdc++.h>
using namespace std;
const int MAXN=300010;
int n,q,f,t,d,totpre,totsuf;
char c[MAXN],tmp[6],pre[MAXN],suf[MAXN];
int main () {
	scanf("%s",c+1);
	n=strlen(c+1);
	scanf("%d",&q);
	for (int i=1;i<=q;i++) {
		scanf("%d",&t);
		if (t==1) {
			d^=1;
		} else {
			scanf("%d%s",&f,tmp+1);
			if (d^(f-1)) {
				suf[++totsuf]=tmp[1];
			} else {
				pre[++totpre]=tmp[1];
			}
		}
	}
	if (d) {
		for (int i=totsuf;i>=1;i--) {printf("%c",suf[i]);}
		for (int i=n;i>=1;i--) {printf("%c",c[i]);}
		for (int i=1;i<=totpre;i++) {printf("%c",pre[i]);}
	} else {
		for (int i=totpre;i>=1;i--) {printf("%c",pre[i]);}
		for (int i=1;i<=n;i++) {printf("%c",c[i]);}
		for (int i=1;i<=totsuf;i++) {printf("%c",suf[i]);}
	}
	printf("\n");
	return 0;
}

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

int N;
int W;
long long w[100010];
long long v[100010];
long long dp[110][100010];

int main ()
{
    cin >> N >> W;
    for(int i = 0; i < N; i++) cin >> w[i] >> v[i];
    memset(dp, 0, sizeof(dp));

    long long res = 0;
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j <= W; j++)
        {
            if(j - w[i] >= 0)
            {
                dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]);
            }
            else
            {
                dp[i + 1][j] = dp[i][j];
            }
            if(i + 1 == N) res = max(res, dp[N][j]);
        }
    }
    cout << res << endl;
}

Measured memory_bytes: 86272
#include <stdio.h>
#include <iostream>
#include <math.h>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>

//#include <tuple>

//#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

bool equalArray(vector<int> v, vector<int> v2, int N){
  for (int i = 0; i < N; i++){
    if (v[i] != v2[i]){
      return false;
    }
  }
  return true;
}

int main() {
  int N, p;
  cin >> N;
  vector<int> v(N);
  vector<int> v2(N);
  for (int i = 0; i < N; i++) {
    cin >> p;
    v[i] = p;
    v2[i] = p;
  }
  sort(v2.begin(), v2.end());
  vector<int> tmp;
  for (int i = 0; i < N; i++){
    if (v[i] != v2[i]){
      tmp.push_back(i);
    }
  }
  // 交換する場合
  if (tmp.size() == 2){
    swap(v[tmp.at(0)], v[tmp.at(1)]);
  }
  // 配列が一致するかチェック
  if(equalArray(v, v2, N)) cout << "YES" << endl;
  else cout << "NO" << endl;
}


Measured memory_bytes: 256
N=int(input())
A=input().split()
B=input().split()
C=input().split()
ans=0
for i in range(0,N):
  ans=ans+int(B[int(A[i])-1])
  if i>0 and int(A[i])>1:
    if int(A[i])==int(A[i-1])+1:
      ans=ans+int(C[int(A[i-1])-1])
print(ans)

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

int main() {
  int n;
  cin >> n;
  vector<vector<int>> a(2, vector<int>(n)), b(2, vector<int>(n));
  rep(i, 2) rep(j, n) cin >> a[i][j];

  b[0][0] = a[0][0];
  for (int i = 1; i < n; i++) b[0][i] = b[0][i - 1] + a[0][i];

  b[1][n - 1] = a[1][n - 1];
  for (int i = n - 2; i >= 0; i--) b[1][i] = b[1][i + 1] + a[1][i];

  int maxcandy = 0;
  rep(i, n) { maxcandy = max(maxcandy, b[0][i] + b[1][i]); }
  cout << maxcandy << endl;
  return 0;
}


Measured memory_bytes: 256
s=input()
alp="".join([chr(i) for i in range(97,97+26)])
if len(s)<26:
    for i in alp:
        if i not in s:
            print(s+i)
            exit()
else:
    if s=="".join([chr(i) for i in range(97,97+26)][::-1]):
        print(-1)
    else:
        for i in range(25)[::-1]:
            for j in range(i+1,26)[::-1]:
                if s[i]<s[j]:
                    print(s[:i]+s[j])
                    exit()

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for(ll i=0;i<n;i++)
#define P pair<ll,ll>
#define Graph vector<vector<ll>>
#define INF (1ll<<60)
#define mod 1000000007
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;}

int main(){
    ll n;cin>>n;
    vector<ll> a(n);
    rep(i,n) cin>>a[i];

    ll num=a[0];
    rep(i,n){
        if(i==0) continue;

        num=num^a[i];
    }

    rep(i,n){
        cout<<(num^a[i])<<" ";
    }
    cout<<endl;
    return 0;
}

Measured memory_bytes: 4784
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
 
public class Main {
	static int[]v;
	static int c[];
	static int ans=0;
	static void solve(int i,int val,int cost) {
		ans=Math.max(ans,val-cost);
		if(i>=v.length)return;
		solve(i+1,val,cost);solve(i+1,val+v[i],cost+c[i]);
	}
	public static void main(String[] args) throws IOException {
		MScanner sc = new MScanner(System.in);
		//BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw=new PrintWriter(System.out);
		int n=sc.nextInt();
		v=new int[n];c=new int[n];
		for(int i=0;i<n;i++)v[i]=sc.nextInt();
		for(int i=0;i<n;i++)c[i]=sc.nextInt();
		solve(0,0,0);
		pw.println(ans);
		pw.close();
		pw.flush();
 
	}

    static class MScanner {
		StringTokenizer st;
		BufferedReader br;
 
		public MScanner(InputStream system) {
			br = new BufferedReader(new InputStreamReader(system));
		}
 
		public MScanner(String file) throws Exception {
			br = new BufferedReader(new FileReader(file));
		}
 
		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
 
		public String nextLine() throws IOException {
			return br.readLine();
		}
 
		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
 
		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}
 
		public char nextChar() throws IOException {
			return next().charAt(0);
		}
 
		public Long nextLong() throws IOException {
			return Long.parseLong(next());
		}
 
		public boolean ready() throws IOException {
			return br.ready();
		}
 
		public void waitForInput() throws InterruptedException {
			Thread.sleep(3000);
		}
	}
}

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<ll, pair<ll, ll> > P3;

const ll MOD = ll(1e9 + 7);
const ll LLINF = LLONG_MAX;
const int IINF = INT_MAX;
const int MAX_V = int(1e3) + 3;
const double EPS = 1e-8;
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
#define SORT(v) sort((v).begin(), (v).end())
#define SORTR(v) sort((v).rbegin(), (v).rend())
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)

ll d,p[15]{},c[15]{},g;
bool isfull[15]{};

ll rec(ll k, ll x){
    ll res=0;
    res += k*100*min(x,p[k]);
    if(x>=p[k]) res += c[k];
    x -= min(x,p[k]);
    isfull[k] = true;
    if(x>0){
        ll rmax = 0;
        FOR(i,1,d+1){
            if(isfull[i])continue;
            rmax = max(rmax,rec(i,x));
        }
        res += rmax;
    }
    isfull[k] = false;
    return res;
}

ll bs(){
    ll ok = 1000, ng = 0;
    while(abs(ok-ng)>1){
        ll mid = (ok+ng)/2;
        if(rec(0,mid)>=g){
            ok = mid;
        }
        else{
            ng = mid;
        }
    }
    return ok;
}

int main() {
    cin >> d >> g;
    REP(i,d){
        cin >> p[i+1] >> c[i+1];
    }
    cout << bs() << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<iomanip>
#include<sstream>
#include<map>
#include<cmath>
using namespace std;
#define rep(i,n) for(int i = 0;i < n;i++)
#define req(i,n) for(int i = 1;i <=n;i++)
#define rrep(i,n) for(int i = n -1;i >= 0;i--)
#define ALL(a) a.begin(),a.end()
typedef long long ll;
typedef long double ld;
const ll MOD =  1000000007;
const ll INF =  1LL << 60;
int n, m, x, y;ll z = 0, w, h, sum = 0, ans;
template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T & val) {
    std::fill((T*)array, (T*)(array + N), val);
}
int main(void) {
    cin >> n >> m; map<int, int> mp;
    mp[0]++;
    rep(i, n) {
        cin >> x; z += x; z %= m;
        sum += mp[z];
        mp[z]++;
    }cout << sum << endl;
}

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

typedef long long ll;

using namespace std;

int n,m;

int main() {
	cin >> n >> m;
	vector<ll> arr(m);
	for(int i = 0; i < m; i++) {
		cin >> arr[i];
	}
	sort(arr.begin(),arr.end());
	vector<ll> dist(m-1);
	for(int i = 0; i < m-1; i++) {
		dist[i] = arr[i+1]-arr[i];
	}
	sort(dist.begin(),dist.end());

	ll ans = 0;
	for(int i = 0; i < m-n; i++) {
		ans += dist[i];
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 1792
//
//  main.cpp
//  APG4b
//
//  Created by 安藤光希 on 2020/03/21.
//  Copyright © 2020 安藤光希. All rights reserved.
//


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

int main() {
    ll N;
    cin >> N;
        
    if(N==0){
        cout << 2 << endl;
    } else if (N == 1){
        cout << 1 << endl;
    } else {
        vector<ll> S(N+1, 0);
        S[0] = 2;
        S[1] = 1;
        
        for(int i = 2; i < N + 1; i++){
            S[i] = S[i-1] + S[i-2];
        }
        cout << S[N] << endl;

    }
}


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

using namespace std;

#define YES cout << "YES" << endl;
#define NO  cout << "NO"  << endl;
#define Yes cout << "Yes" << endl;
#define No  cout << "No"  << endl;
 
#define INF INT_MAX
#define MOD 1000000007
#define PI  acos(-1)

using ll  = long long;
using ull = unsigned long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

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

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

    ll N, X;
    cin >> N >> X;

    vector<ll> L(N); 
    rep (i, N) {
        cin >> L[i];
    }

    ll count = 0;
    ll sum = 0;
    rep (i, N+1) {
        if (X >= sum) {
            count++;
        }
        sum += L[i];
    }

    cout << count << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
#include<stdio.h>
#include <cstdint>
#include <stdlib.h> 
#include <time.h>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define rrep(i,n) REP(i,1,n+1)
#define all(a) a.begin(), a.end()
#define fi first
#define se second
#define RNG(x, a, n) &((x)[a]), &((x)[n])
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
typedef long long ll;
typedef pair<ll, ll> Pll;
typedef pair<int, int> PII;
typedef vector<ll> Vl;
typedef vector<int> VI;
typedef tuple<int, int, int> TT;
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
#define rall(v) v.rbegin(), v.rend()
#define dmp(x,y) make_pair(x,y)
#define dmt(x, y, z) make_tuple(x, y, z)
#define pb(x) push_back(x)
#define pf(x) push_front(x)
const int MAX = 5100000;
const int inf = 1e9 + 7;
const int mod = 1e9 + 7;
const ll longinf = 1LL << 60;
const long double PI = (acos(-1));
const long double EPS = 0.0000000001;


int n, k;
int d[10];

int main() {

	cin >> n >> k;
	rep(i, k)cin >> d[i];
	
	while (true) {
		bool f = false;
		VI vec;
		int tmp = n;

		while (tmp) {
			vec.pb(tmp % 10);
			tmp /= 10;
		}

		rep(i, vec.size()) {
			rep(j, k) {
				if (vec[i] == d[j]) {
					f = true;
					break;
				}
			}
			if (f)break;
		}
		if (f) {
			n++;
			continue;
		}
		else {
			cout << n << endl;
			break;
		}
	}

	return 0;
}

Measured memory_bytes: 256
const Main = input => {
    const x = parseInt(input, 10);
    let yokin = 100;
    let count = 1;
    while(true) {
        yokin += Math.floor(yokin * 0.01);

        if(yokin >= x) break;
        count++;
    }
    console.log(count);
}

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

Measured memory_bytes: 29736
#include<iostream>
#include<string>
#include<algorithm>
#include<math.h>
#include<queue>
#include<set>
#include<map>
#include<random>
#include<functional>
#include<utility>

typedef long long ll;

#define rep(i,n) for(int i=0; i<n; i++)
#define pb push_back
#define P pair<int, int>
#define PLI pair<ll, int>
#define PLL pair<ll, ll>
#define VI vector<int>
#define VII vector<VI>

using namespace std;


int N, T, S;
int A[3005], B[3005];
int dp[3005] = {};
int main() {
	cin >> N >> T >> S;
	rep(i, N) cin >> A[i] >> B[i];
	rep(i, N)for(int j=T-1; j>=0; j--) {
		dp[j + 1] = max(dp[j+1], dp[j]);
		if (j + B[i] > T) continue;
		if (j+B[i]<=S || S <= j) {
			dp[j + B[i]] = max(dp[j + B[i]], dp[j] + A[i]);
		}
	}
	int ans = 0;
	rep(i, T + 1) ans = max(ans, dp[i]);
	cout << ans << endl;

	return 0;
}



Measured memory_bytes: 3160
import sys
if sys.platform =='ios':
	sys.stdin=open('input.txt')
	
n = int(input())

a,b = map(int,input().split())

l = list(map(int,input().split()))
k = [0]*3

for i in range(n):
	if l[i]<=a:
		k[0]=k[0]+1
	elif a<l[i]<=b:
		k[1]=k[1]+1
	elif b<l[i]:
		k[2]=k[2]+1

print(min(k))

Measured memory_bytes: 38384
import java.util.Scanner;
import java.lang.Math;

class Main {

    public static class Tuple{
        public final double x;
        public final double y;
        public Tuple(double x, double y) {
            this.x = x;
            this.y = y;
        }
        public void print(){
            System.out.printf("%f %f\n", x, y);
        }
    }

    static void koch(int n, Tuple a, Tuple b){
        if (n == 0) return;

        Tuple s, t, u;
        double cos60 = Math.cos(Math.PI * 60.0 / 180.0);
        double sin60 = Math.sin(Math.PI * 60.0 / 180.0);
        s = new Tuple((2.0 * a.x + 1.0 *b.x) / 3.0, (2.0 * a.y + 1.0 * b.y) / 3.0);
        t = new Tuple((1.0 * a.x + 2.0 *b.x) / 3.0, (1.0 * a.y + 2.0 * b.y) / 3.0);
        u = new Tuple((t.x - s.x) * cos60 - (t.y - s.y) * sin60 + s.x,
                      (t.x - s.x) * sin60 + (t.y - s.y) * cos60 + s.y);

        koch(n - 1, a, s);
        s.print();
        koch(n - 1, s, u);
        u.print();
        koch(n - 1, u, t);
        t.print();
        koch(n - 1, t, b);
    }

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

        int n = sc.nextInt();
        Tuple a = new Tuple(0.0,0.0);
        Tuple b = new Tuple(100.0,0.0);

        a.print();
        koch(n,a,b);
        b.print();
    }
}



Measured memory_bytes: 40916
#include <iostream>
#include <fstream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
#define REP(i,n) for(int i = 1; i<=n; ++i)
#define all(x) begin(x),end(x)
#define show(obj) {for(auto x:obj)cout<<x<<' ';cout<<endl;}
#define line "----------"
typedef long long ll;
typedef pair<int,int> P;
const int inf = 2147483647;
const ll INF = 1LL<<60;
const int MOD = (int)1e9 + 7;

//RMQ_Segment_Tree
int initial = 0;
int N, dat[1000000];
void init(int n_){
	N = 1;
	while(N<=n_)N *= 2;
	for(int i = 1; i<=2*N; ++i)dat[i] = initial;
}

void update(int k, int a){
	k += N-1;
	dat[k] += a;
	while(k>0){
		k /= 2;
		dat[k] = dat[k*2] + dat[k*2+1];
	}
}

int query(int a, int b, int k, int l, int r){
	if(r <= a || b <= l)return initial;
	if(a <= l && r <= b)return dat[k];
	else{
		int vl = query(a, b, k*2, l, (l+r)/2);
		int vr = query(a, b, k*2+1, (l+r)/2, r);
		return vl+vr;
	}
}

int main(){
	int n,q; cin>>n>>q;
	init(n);
	// cout<<N<<endl;
	rep(i,q){
		int Q,a,b;
		cin>>Q>>a>>b;
		// cout<<dat[1]<<endl;;
		if(Q == 0){
			update(a+1, b);
		}else{
			cout<<query(a, b+1, 1, 1, N)<<endl;
		}
	}
	return 0;
}


Measured memory_bytes: 4108
{-# LANGUAGE BangPatterns #-}
import Control.Arrow
import Control.Monad.Fix
import Data.Char
import Data.Int
import Data.Foldable
import Data.List
import qualified Data.Vector as V
import qualified Data.Vector.Unboxed as VU
import qualified Data.ByteString.Char8 as B
import Debug.Trace

solve :: B.ByteString -> VU.Vector Int
solve !bs = VU.accum (+) (VU.replicate (B.length bs) 0) $ zip coords [1, 1 ..]
 where
  coords = reverse $ (\(ans, _, _, _) -> ans) $ B.foldl'
    ( \(!ans, !ps, !prev, !i) (!cur) ->
      let ps' = if prev == 'L' && cur == 'R' then tail ps else ps
          p   = head ps'
      in  ((if even (p - i) then p else p - 1) : ans, ps', cur, i + 1)
    )
    ([], points, B.head bs, 0)
    bs

  points = reverse $ (\(_, !acc, _) -> acc) $ B.foldl'
    ( \(!prev, !acc, !i) (!cur) ->
      (cur, if prev == 'R' && cur == 'L' then i : acc else acc, i + 1)
    )
    (B.head bs, [], 0 :: Int)
    bs

main = do
  let readInt :: Integral a => B.ByteString -> Maybe (a, B.ByteString)
      readInt = fmap (first fromIntegral . second B.tail) . B.readInt

  bs <- B.getLine
  putStrLn $ intercalate " " $ map show $ VU.toList $ solve bs


Measured memory_bytes: 17532
#include<bits/stdc++.h> 
using namespace std;
#define ll long long
#define mod 1000000007ll
#define vll vector<ll>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define pb push_back
#define mp make_pair
#define x first
#define y second
#define db(x) cout << #x << " = " << x << '\n'
#define sep cout << "\n********************************************\n"
#define fast  ios_base::sync_with_stdio(false), cin.tie(NULL)
ll n, m;
pll cost[1003];
ll dp[2][1 << 12];
int main(int argc, char const *argv[])
{
	cin >> n >> m;
	for (int i = 0; i < m; ++i)
	{
		ll sz;
		cin >> cost[i].x >> sz;
		ll mask = 0;
		while (sz --)
		{
			ll id;
			cin >> id;
			id --;
			mask |= (1ll << id);
		}
		cost[i].y = mask;
	}
	memset(dp, -1, sizeof(dp));
	dp[1][0] = 0;
	for (int i = 0; i < m; ++i)
	{
		ll f = (i & 1);
		for (int j = 0; j < (1 << n); ++j)
		{
			dp[f][j] = dp[1 - f][j];
		}
		for (int j = 0; j < (1 << n); ++j)
		{
			if (dp[1 - f][j] == -1)
				continue;
			if (dp[f][j | cost[i].y] == -1)
				dp[f][j | cost[i].y] = dp[1 - f][j] + cost[i].x;
			else
				dp[f][j | cost[i].y] = min(dp[f][j | cost[i].y], dp[1 - f][j] + cost[i].x);
		}
	}
	cout << dp[(m - 1) & 1][(1 << n) - 1];
	return 0;
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
//long long int countt[200003];
#include<ext/pb_ds/assoc_container.hpp> // include the associative containers or group of templates such as set, multimap, map etc.
#include<ext/pb_ds/tree_policy.hpp> // include the tree_order_statistics_node update
using namespace __gnu_pbds; //necessary for the GNU based Policy based data structures.
typedef tree<pair<int,int> ,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

#define int long long
#define f first
#define s second
signed main()
{
    FAST;
    
    int i=0,j=0,k=0,n=0,m=0,count=0,temp=0,z;
    int temp1=0,temp2=0,temp3=0,x=0,l=0,y=0,sum=0;
    int ans=0;
    
    
    cin>>n;
    int a[n];
    map<int,int> mp;
    for(i=0;i<n;i++)
    {
        cin>>a[i];
        mp[a[i]]++;
        
    }
    ans=0;
    for(auto it : mp)
    {
        temp = it.second;
        ans = ans + (((temp)*(temp-1))/2);
    }
    
    
    map<int,int> mp1;
    
    for(auto it: mp)
    {
        temp = it.second;
        sum=0;
        if(temp>=2)
        {
        sum = ans - (((temp)*(temp-1))/2);
        
        sum = sum + (((temp-1)*(temp-2))/2);
        
        mp1[it.first]=sum;
        }
        
        else
        {
            mp1[it.first]=ans;
        }
    }
    
    
    for(i=0;i<n;i++)
    {
        cout<<mp1[a[i]]<<endl;
    }
    
    
    
    
}


Measured memory_bytes: 20864
def die(): print(-1); exit()

s = input()
n = len(s)
if s[-1] == '1': die()
if s[0] == '0': die()
for i in range(n-1):
    if s[i] != s[-i-2]: die()

root = last = 1
for i in range(n-1):
    last+= 1
    print(root, last)
    if s[i] == '1': root = last

Measured memory_bytes: 4648
#include<stdio.h>
int main(void)
{
	int a[100];
	int N,i,j,minj,x;
	int cunt=0;
	
	scanf("%d",&N);
	for(i=0;i<N;i++)scanf("%d",&a[i]);
	
	for(i=0;i<N-1;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)cunt++;
	}
	for(i=0;i<N;i++){
		if(i>0)printf(" ");
		printf("%d",a[i]);
	}
	printf("\n%d\n",cunt);
	return 0;
}

Measured memory_bytes: 604