akhauriyash/Code-Regression huggingface dataset:
# coding: utf-8


def solve(*args: str) -> str:
    s = args[0]
    k = int(args[1])

    if all([s[0] == c for c in s]):
        return str(int(len(s) * k / 2))

    H = s[0]

    ret = 0
    h = 1
    t = 0
    while H == s[h] and h < len(s):
        h += 1

    while H == s[-t-1] and t < len(s):
        t += 1

    ret += int((h + t) / 2) * (k - 1) + int(h/2) + int(t/2)

    m = 1
    for i in range(h, len(s) - t - 1):
        if s[i] == s[i+1]:
            m += 1
        else:
            ret += int(m/2) * k
            m = 1

    if 1 < m:
        ret += int(m/2) * k

    return str(ret)


if __name__ == "__main__":
    print(solve(*[input() for _ in range(2)]))


Measured memory_bytes: 38256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//cout << fixed << setprecision(17) << res << endl;
 

int main() {
    ll n;
    cin >> n;
    vector<ll> pow6s;
    vector<ll> pow9s;
    ll cur = 1;
    while (cur <= n) {
        cur *= 6;
        pow6s.push_back(cur);
    }
    cur = 1;
    while (cur <= n) {
        cur *= 9;
        pow9s.push_back(cur);
    }
    
    vector<ll> dp(n+1, 1e9);
    dp[0] = 0;
    for (ll i = 0; i < n; ++i) {
        dp[i+1] = min(dp[i+1], dp[i] + 1);
        for (auto p : pow6s) {
            if (i+p > n) break;
            dp[i+p] = min(dp[i+p], dp[i] + 1);
        }
        for (auto p : pow9s) {
            if (i+p > n) break;
            dp[i+p] = min(dp[i+p], dp[i] + 1);
        }
    }
    cout << dp[n] << endl;
}


Measured memory_bytes: 1024
#include  <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 1000000007
//vector<vector<int>> vec(縦, vector<int>(横));
#define REP(i,N) for(int i=0;i<N;i++)
int gcd(int a, int b) {
    if(a>b){
        swap(a,b);
        }
    while(b%a!=0){
        b%=a;
        swap(a,b);
    }
    return a;
}


//cout << setprecision(123)<<ans;
//a=atoi(S.c_str());
//S=to_string(a);
//int &a=b;
int main(){
  int N;
  cin>>N;
  int X=floor(N/1.08);
  int Y=X+1;
  
  if(Y<(N+1)/1.08&&floor(Y*1.08)==N)cout<<Y<<endl;
  else if(X<(N+1)/1.08&&floor(X*1.08)==N)cout<<X<<endl;
  else cout<<":("<<endl;
}


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

typedef pair<int, int> P;

int main() {

    string s,t;
    cin >> s >> t;
    bool ok;
    bool ok2 = false;
    int n = -1;
    rep(i,s.size()-t.size()+1){
        if(s[i]=='?'||s[i]==t[0]){
            ok = true;
            rep(j,t.size()){
                if(s[i+j]!='?'&&s[i+j]!=t[j]){
                    // cout << "break with " << s[i+j] << t[j] << endl;
                    ok = false;
                    break;
                }

            }
            if(ok)n = i;
        }
    }

    if(n>=0){
        s = s.substr(0,n) + t + s.substr(n+t.size());
        ok2 = true;
    }

    rep(i,s.size()){
        if(s[i]=='?'){
            s[i] = 'a';
        }
    }

    if(ok2){
        cout << s  << endl;
    }else{
        cout << "UNRESTORABLE" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
s = input()

import numpy as np
B = []
W = []
for i in range(len(s)):
    if s[i] == "B":
        B.append(i)
    elif s[i] == "W":
        W.append(i)

print(sum(np.array(W) - np.array([i for i in range(len(W))])))

Measured memory_bytes: 45840
#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<math.h>
#include<utility>
#include<climits>

using namespace std;

int main(){
	int n,k;
	cin>>n>>k;
	vector<int> dp(k+1);
	int ar[n];
	for(int i=0;i<n;i++)
		cin>>ar[i];
	dp[0]=0;
	for(int i=1;i<=k;i++){
		int temp=0;
		for(int j=0;j<n;j++){
			if(i-ar[j]<0 || dp[i-ar[j]] == 1){
				temp = temp | 0;
			}
			else{
				temp = temp | 1;
			}
		}
		dp[i]=temp;
	}
	if(dp[k]==1)
		cout<<"First";
	else
		cout<<"Second";
}


Measured memory_bytes: 640
#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;
int p[20];
int q[20];
char str[5][5];
int bfs[1<<16];
char col[5]="RGB";
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++){
		scanf("%d%d",p+i,q+i);
	}
	for(int i=0;i<4;i++)scanf("%s",str[i]);
	for(int i=0;i<(1<<16);i++)bfs[i]=-1;
	bfs[0]=0;
	queue<int>Q;
	Q.push(0);
	while(Q.size()){
		if(~bfs[(1<<16)-1])break;
		int at=Q.front();
		Q.pop();
		for(int i=0;i<a;i++){
			for(int j=-p[i]+1;j<4;j++){
				for(int k=-q[i]+1;k<4;k++){
					for(int c=0;c<3;c++){
						int to=at;
						for(int l=max(0,-j);l<min(p[i],4-j);l++)for(int m=max(0,-k);m<min(q[i],4-k);m++){
							//if(j+l<0||k+m<0||j+l>3||k+m>3)continue;
							if(str[j+l][k+m]==col[c])to|=(1<<((j+l)*4+k+m));
							else to&=(~(1<<((j+l)*4+k+m)));
						}
						if(!~bfs[to]){
							bfs[to]=bfs[at]+1;
							Q.push(to);
						}
					}
				}
			}
		}
	}
	printf("%d\n",bfs[(1<<16)-1]);
}

Measured memory_bytes: 1440
#include <iostream>
#include <stdio.h>
#include <string>
#include <algorithm>
#include <vector>
#include <math.h>
#include <numeric>
#include <queue>
#include <numeric>
#include <iomanip>
#include <sstream>
#include <cmath>
#include <map>
#include <functional>
#include <limits>
#include <set>
#define rep(i,a,b) for((i)=a;i<(int)(b);i++)
#define max(a,b) (a < b ? b : a)
#define min(a,b) (a > b ? b : a)
#define AAA (1000000007)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;



ll gcd(ll a, ll b) {
	if (b == 0)return a;
	return gcd(b, a % b);
}

ll lcm(ll a,ll b) {
	return a / gcd(a, b) * b;
}


int main() {
	int i, j, k;
	ll N, M, K;
	ll ans = 0;


	cin >> N >> M;
	cout << N / M + ((N % M != 0) ? 1 : 0);

	return 0;


}


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

int main() {
  int n, k, i, sum = 1;
  
  cin >> n >> k;
  
  for(i = 0; i < n; i++)
  {
    if(sum < k)
      sum *= 2;
    else
      sum += k;
  }
  
  cout << sum << endl;
}

Measured memory_bytes: 384
#include <stdio.h>
int main(){
  int h,w,i,j;

  while(1){

    scanf("%d%d",&h,&w);

    if(h==0 && w==0) break;

    
    for(j=0;j<w;j++) printf("#");

    printf("\n");

    for(i=1;i<h-1;i++){
      printf("#");
      for(j=1;j<w-1;j++){
	printf(".");
      }
      printf("#\n");
    }

    for(i=0;i<w;i++)printf("#");

    printf("\n\n");
   
  }
  return 0;
}

Measured memory_bytes: 588
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef long long  ll;
#define rep(i,s,n)for(ll i=s;i<n;i++)
#define repe(i,s,n)for(ll i=s;i<=n;i++)

static const ll MOD = 1e9 + 7;
static const ll INF = (ll)1 << 62;

static const ll MAX_N = 100001;
static const ll MAX_M = 200001;

ll V;
ll d[MAX_N] = {};
struct edge { ll to, cost; };
typedef pair<ll, ll> P;
vector<edge> G[MAX_N];
priority_queue <P, vector<P>, greater<P>> que;
bool mst[MAX_N];

ll cost = 0;

bool complete() {
	ll cnt = 0;
	rep(i, 0, V) {
		if (mst[i])cnt++;
	}
	return (cnt == V);
}

void prim(ll s) {
	fill(d, d + V, INF);
	d[s] = 0;
	que.push(P(0, s));

	while (!que.empty()) {
		P p = que.top(); que.pop();
		ll v = p.second;
		if (mst[v])continue;

		cost += p.first;
		mst[v] = true;

		rep(i, 0, G[v].size()) {
			edge e = G[v][i];
			if (!mst[e.to]) {
				que.push(P(e.cost, e.to));
			}
		}

		if (complete())break;
	}
}

int main() {
	//freopen("C://testcase//in7.txt", "r", stdin);

	ll E; cin >> V >> E;
	rep(i, 0, E) {
		ll s, t, d; cin >> s >> t >> d;
		G[s].push_back(edge{ t,d });
		G[t].push_back(edge{ s,d });
	}

	prim(0);

	cout << cost << endl;

	return 0;
}


Measured memory_bytes: 12612
#include <iostream>
#include <string>

using namespace std;

string s, t;

int main()
{
    cin >> s >> t;
    string ret = "No";

    for (int i = 0; i < s.length(); i++) {
        if (s == t) {
            ret = "Yes";
            break;
        }
        // rotation
        char x = s[s.length() - 1];
        for (int j = s.length() - 1; j >= 0; j--) {
            if (j == 0) s[j] = x;
            else        s[j] = s[j - 1];
        }
    }

    cout << ret << endl;

    return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CSharp_AtCoder
{
    class Program
    {

        const long MOD = 1000000000 + 7;

        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            long[] A = Console.ReadLine().Split(' ').Select(s => long.Parse(s)).ToArray();

            long ans = 0;
            for(int k = 0; k < 60; k++)
            {
                // A の k bit目の1と0の数をカウント
                long ak_0 = 0;
                long ak_1 = 0;
                for(int i = 0; i < N; i++)
                {
                    // A[i]の k bit目の値
                    int ai_k = (int)(A[i] >> k) & 1;

                    if (ai_k == 0) ak_0++;
                    else ak_1++;
                }

                // 2^k 乗を計算
                long k_exp2 = 1;
                for(int j = 0; j < k; j++)
                {
                    k_exp2 *= 2;
                    k_exp2 %= MOD;
                }

                // 1 と 0 の組み合わせは ak_0 * ak_1個
                long sum = (ak_1 * ak_0) % MOD;
                ans += (sum * k_exp2) % MOD;
                ans %= MOD;
            }

            Console.WriteLine(ans);
        }
    }
}


Measured memory_bytes: 60328
using System;
using System.Linq;
namespace AtCoder_Begginer_Contest1
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] NM = Console.ReadLine().Split();
            int N = int.Parse(NM[0]);
            int M = int.Parse(NM[1]);
            string ans = "No";
            if (N == M) ans = "Yes";
            Console.WriteLine(ans);
        }
    }
}

Measured memory_bytes: 11092
#include <bits/stdc++.h>
#define len(v) ((int)((v).size()))
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define chmax(x, v) x = max((x), (v))
#define chmin(x, v) x = min((x), (v))
using namespace std;
using ll = long long;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	vector<string> o {"AC", "WA", "TLE", "RE" };
	vector<int> res(4,0);
	int n; cin >> n;
	for (int i = 0; i < n; ++i) {
		string s; cin >> s;
		for (int k = 0; k<4; ++k) {
			if (s == o[k]) ++res[k];
		}
	}
	for (int i = 0; i < 4; ++i) {
		cout << o[i] << " x " << res[i] << "\n";
	}
}


Measured memory_bytes: 3676
#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;
    int nn = n % 10;
    if (nn == 3) {
        cout << "bon" << endl;
    } else if (nn == 0 || nn == 1 || nn == 6 || nn == 8) {
        cout << "pon" << endl;
    } else {
        cout << "hon" << endl;
    }

    return 0;
}

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

using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
#define rep(i,n) for(ll i = 0;i < (ll)n;i++)
#define ALL(x) (x).begin(),(x).end()
#define MOD 1000000007


struct edge{
  ll to,we;
};

int main(){
  
  int n,m;
  cin >> n >> m;
  vector<vector<edge>> v(n);
  rep(i,m){
    int fr,to,we;cin >> fr >> to >> we;
    fr--,to--;
    v[fr].push_back({to,we});
    v[to].push_back({fr,-we});
  }
  vector<ll> dist(n,-(1ll << 60));
  bool is = true;
  rep(i,n){
    if(dist[i] != -(1ll << 60))continue;
    queue<int> que;
    que.push(i);
    dist[i] = 0;
    while(!que.empty()){
      int ov = que.front();que.pop();
      for(auto nv : v[ov]){
        if(dist[nv.to] != -(1ll << 60)){
          if(dist[nv.to] != dist[ov]+nv.we)is = false;
        }else{
          dist[nv.to] = dist[ov] + nv.we;
          que.push(nv.to);
        }
      }
    }
  }
  is ? cout << "Yes" << endl : cout << "No" << endl;



  

  return 0;
}


Measured memory_bytes: 13824
import collections

n, m = map(int, input().split())

counter = collections.Counter()
for _ in range(n):
    k, *la = map(int, input().split())
    for x in la:
        counter[x] += 1
res = 0
for x in counter.values():
    if x == n:
        res += 1
print(res)

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

int main(){
    string S;
    cin >> S;
    if (S == "ABC") cout << "ARC" << endl;
    else cout << "ABC" << endl;
}


Measured memory_bytes: 3624
using System;
using System.Diagnostics;
using System.IO;
using System.Text;
using System.Linq;
using System.Collections.Generic;
using System.Text.RegularExpressions;

class Program
{
    const string Yes = "Yes";
    const string No = "No";
    const char White = '.';
    const char Black = '#';
    const long Mod = 1000000007;

    static void Main(string[] args) {
#if DEBUG
        MyDebugger.Test(process, "../TextFile1.txt");
#else
        object ret = process(new StreamReader(Console.OpenStandardInput()));
        Console.WriteLine(ret);
#endif
    }

    static object process(TextReader input) {
        var s = input.ReadLine();
        s = s.Replace(" ", "");

        var x = int.Parse(s);

        for(long i=1; i<100100; i++) {
            if(x == i*i) return Yes;
        }

        return No;
    }

    static int[] ToIntArray(string strs, int n) {
        var ret = new int[n];
        var spl = strs.Split(' ');
        for (int i = 0; i < n; i++)
            ret[i] = int.Parse(spl[i]);
        return ret;
    }

}


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

int main() {
  int n, x, t;
  
  cin >> n >> x >> t;
  
  int a = n / x;
  
  if(n % x != 0){
    cout << a * t + t << endl;
  }
  else{
    cout << a * t << endl;
  }
  

}
 
 //vector<int> a(3);
 //a.at(0);
 //a.size();
 //vector<vector<int>> a(3, vector<int>(3));
 //uint64_t sum = 0;
 //max(a, b);
 //min(a, b);
 //swap(a, b);
 //sort(vec.begin(), vec.end());  昇順
 //reverse(vec.begin(), vec.end());  降順


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

int main()
{
	int n, m;

	cin >> n >> m;

	int left = 1, right = n;

	for (int i = 0; i < m; i++)
	{
		int l, r;

		cin >> l >> r;

		left = max(left, l);
		right = min(right, r);
	}

	if (left > right)
		cout << 0 << endl;
	else
		cout << right - left + 1 << endl;

	return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC142
{
    class A
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            double ans = ((n + n % 2) / 2.0) / n;
            Console.WriteLine(ans);
        }
    }
}


Measured memory_bytes: 11092
N, K = map(int, input().split())
LR = [[int(i) for i in input().split()] for _ in range(K)]

mod = 998244353

class BinaryIndexedTree() :
  def __init__(self, n, mod) :
    self.n = n
    self.mod = mod
    self.tree = [0] * (n + 1)
      
  def sum(self, i) :
    s = 0
    while i > 0 :
      s += self.tree[i]
      i -= i & -i
    return s
      
  def add(self, i, x) :
    while i <= self.n :
      self.tree[i] += x
      self.tree[i] %= mod
      i += i & -i
      
BIT = BinaryIndexedTree(N * 2, mod)
BIT.add(1, 1)
BIT.add(2, -1)
for i in range(1, N) :
  for l, r in LR :
    x = BIT.sum(i)
    BIT.add(i + l, x)
    BIT.add(i + r + 1, -x)

print(BIT.sum(N) % mod)

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

int main(){
	string s;
	string a[] = {"Sunny", "Cloudy", "Rainy"};
	cin >> s;
	string ans;
	if(s ==a[0]) ans = a[1];
	if(s ==a[1]) ans = a[2];
	if(s ==a[2]) ans = a[0];
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i,a) repi(i,0,a)
const int MAX = 100010;
int N, M;
typedef pair<int,int> pii;

struct union_find{
    int rnk[MAX], par[MAX], w[MAX];

    union_find(int n){ rep(i,n) rnk[i] = 1, par[i] = i, w[i] = 0;}

    pii weight(int x){
        if(x == par[x]) return pii(x,0);
        pii ret = weight(par[x]);
        return pii((par[x]=ret.first), (w[x]+=ret.second));
    }
    int find(int x){ return weight(x).first;}
    void unite(int a, int b, int k){
        int x = find(a), y = find(b);
        k -= w[b]-w[a];
        if(x == y) return;
        if(rnk[x] > rnk[y]){
            par[y] = x;
            w[y] = k;
        }
        else{
            par[x] = y;
            w[x] = -k;
            if(rnk[x] == rnk[y]) rnk[y]++;
        }
    }
    bool same(int x, int y){ return find(x)==find(y);}
};

void solve(){
    union_find uf(N);
    int a, b, w; char c;
    rep(i,M){
        cin >> c >> a >> b; a--; b--;
        if(c=='!'){
            cin >> w;
            uf.unite(a,b,w);
        }
        else {
            if(!uf.same(a,b)) puts("UNKNOWN");
            else cout << uf.w[b]-uf.w[a] << endl;
        }
    }
}

int main(){
    while(cin >> N >> M, N and M) solve();
    return 0;
}

Measured memory_bytes: 4256
#include<bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define vvi vector<vi>
#define vs vector<string>
#define pb push_back
#define P pair<int,int>
#define vp vector<P>
#define PP pair<int,P>
#define vpp vector<PP>
#define fi first
#define se second
#define INF (1<<30)
#define MOD 1000000007
#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++)
#define all(x) (x).begin(),(x).end()
int main(){
    int a,b;
    cin>>a>>b;
    string st;
    cin>>st;
    bool f=true;
    REP(i,a){
        if('0'<=st[i]&&st[i]<='9'){
            continue;
        }
        f=false;
    }
    if(st[a]!='-'){
        f=false;
    }
    REP(i,b){
        if('0'<=st[a+i+1]&&st[a+i+1]<='9'){
            continue;
        }
        f=false;
    }
    if(f){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>//Carefully Crafted by hetp111
using namespace std;
#define int long long
#define double long double
#define all(v) (v).begin(),(v).end()
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int,int>
#define vii vector<pii>
#define MOD (1000000007)
#define MOD2 (998244353)
#define MOD3 (1000000009)
#define PI acos(-1)
#define eps (1e-8)
#define INF (1e18)
#define FASTER ios_base::sync_with_stdio(0);cin.tie(0)
template<class A,class B>ostream&operator<<(ostream&out,const pair<A,B>&a){return out<<"("<<a.first<<","<<a.second<<")";}
template<class A>ostream&operator<<(ostream&out,const vector<A>&a){for(const A &it:a)out<<it<<" ";return out;}
template<class A,class B>istream&operator>>(istream&in,pair<A,B>&a){return in>>a.first>>a.second;}
template<class A>istream&operator>>(istream&in,vector<A>&a){for(A &i:a)in>>i;return in;}
ifstream cinn("input.txt");ofstream coutt("output.txt");

signed main(){
    FASTER;
    string a,b;cin>>a>>b;
    if(b.size()-1==a.size()){
        int ok=1;
        for(int i=0;i<a.size();i++){
            ok&=(a[i]==b[i]);
        }
        if(ok){
            cout<<"Yes";
        }else cout<<"No";
    }else cout<<"No";
}

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

using namespace std;

typedef long long ll;
typedef vector<ll> vl;
typedef long double ld;
typedef vector<ld> vd;
typedef bool bl;
typedef vector<bl> vb;
typedef unordered_map<ll,unordered_map<ll,ll>> graph;

const ll e5 = 1 << 20;
const ll mod = 1000000007;
const ll e3 = 1 << 13;
const ll INF = 1ll << 60;

ll n;
ll w[e5];
ll ans = INF;

int main(){
  cin >> n;
  for(ll i = 1;i <= n;i++){
    cin >> w[i];
  }
  for(ll i = 1;i <= n;i++) w[i] += w[i-1];
  for(ll i = 1;i < n;i++){
    ans = min(ans,abs(w[i]-(w[n]-w[i])));
  }
  cout << ans << endl;


}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<utility>
#include<algorithm>
#include<deque>
using namespace std;
using ll = long long int;


int h, w, D, q;
//vector<vector<int>> a;
map<int, pair<int, int>> a;
vector<int>ret;

int main(void) {
	cin >> h >> w >> D;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			int ai;
			cin >> ai;
			a[ai] = pair<int, int>(i, j);
		}
	}
	cin >> q;
	vector<int> d(h * w + 1, 0);
	for (int i = D + 1; i < h * w + 1; i++) {
		pair<int, int> p0 = a[i - D], p1 = a[i];
		d[i] = d[i - D] + abs(p1.first - p0.first) + abs(p1.second - p0.second);
	}

	for (int i = 0; i < q; i++) {
		int li, ri;
		cin >> li >> ri;
		ret.push_back(d[ri] - d[li]);
	}

	for (int i = 0; i < q; i++) {
		cout << ret[i] << endl;
	}
	return 0;
}

Measured memory_bytes: 8952
#include <iostream>
 
using namespace std;
 
int main(){
	string S;
 	cin >> S;
	bool isOk = true;
  
  	for (int i = 0; i < S.size();i++){
    	if(i%2 == 1){
          if(S.at(i)=='R'){
              isOk = false;
          }
        }else
        {
        	if(S.at(i)== 'L'){
              isOk = false;
          }
        }
    }
  
  	if(isOk){
    	cout<<"Yes";
    }else{
    	cout <<"No";
    }
  
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
 
using namespace std;
 
int main()
{
  long long a,b,k;
  cin>>a>>b>>k;
  if(a>k){cout<<a-k<<" "<<b;}
  else if(a+b>=k){cout<<0<<" "<<(a+b)-k;}
  else{cout<<0<<" "<<0;}
  
}

Measured memory_bytes: 256
A=[((a,b,c)=map(x->parse(Int,x),split(s));(b-a,c-b)) for s=readlines()]
if A[1][1]==A[2][1]==A[3][1]&&A[1][2]==A[2][2]==A[3][2]
  println("Yes")
else
  println("No")
end


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

using namespace std;

#define pb push_back
#define eb emplace_back
#define ll long long
#define pii pair < int, int >
#define fr first
#define sc second
#define mk make_pair
#define sz(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define ok puts("ok");
#define whatis(x) cerr << #x << " = " << x << endl;

const int N = (int)1e5 + 7;
const int inf = (int)1e9 + 7;

main() {
  int n;
  scanf("%d", &n);
  int ans = 0;
  for (int i = 1; i <= n; i++) {
    int a, b;
    scanf("%d %d", &a, &b);
    int d;
    while (a % b != 0 && a >= b) {
      d = a / b;
      a -= (d + 1) * ((a % b + d) / (d + 1));
    }
    ans ^= a / b;
  }
  if (ans == 0) {
    puts("Aoki");
  } else {
    puts("Takahashi");
  }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct point
{
	int x,y;
	bool operator<(const point &b)const{return x<b.x||(x==b.x&&y<b.y);}
}a[101];
int n,vis[101];
main()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
	sort(a+1,a+1+n);
	int ans=n;
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
		{
			int p=a[j].x-a[i].x,q=a[j].y-a[i].y,cnt=0;
			if(!p&&!q)continue;
			memset(vis,0,sizeof vis);
			for(int k=1;k<=n;k++)
				if(!vis[k])
				{
					cnt++;
					vis[k]=1;
					int pre=k;
					for(int l=k+1;l<=n;l++)
						if(a[l].x-a[pre].x==p&&a[l].y-a[pre].y==q)vis[l]=1,pre=l;
				}
			ans=min(ans,cnt);
		}
	cout<<ans<<'\n';
}


Measured memory_bytes: 384
def main():
    _ = input()
    A = list(map(int, input().split()))
    A_list = []
    count = 0

    for a in A:
        if a < 0:
            count += 1
            A_list.append(a * -1)
        else:
            A_list.append(a)
    if count % 2 == 0:
        print(sum(A_list))
    else:
        print(sum(A_list)-min(A_list) * 2)


if __name__ == "__main__":
    main()

Measured memory_bytes: 14284
//#include <GOD>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define len length	
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define freo freopen("output.txt","w",stdout)
#define frei freopen("input.txt","r",stdin)

const ll mod=1e9+7;
const ll maxn=2e5+10,maxp=10110;

ll n,ans;
ll a[maxn];

int main(){
	FAST_IO;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	for(int i=1;i<n;i++){
		if(a[i]<a[i-1]){
			ans+=a[i-1]-a[i];
			a[i]=a[i-1];
		}
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 5180
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <ctime>
#include <cstring>
#include <functional>
#include <iostream>
#include <iomanip>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <regex>
#include <vector>

#define fix(n)          cout<<fixed<<setprecision(n)
#define rep(i,n)        for (int i = 0; i < (n); ++i)
#define sort(a)         sort((a).begin(), (a).end())
#define uniq(a)         sort(a);(a).erase(unique((a).begin(), (a).end()), (a).end())
#define reverse(a)      reverse((a).begin(), (a).end())
#define ctos(c)         string(1, (c))
#define out(d)          cout << (d)
#define outl(d)         std::cout<<(d)<<"\n"
#define YES()           cout << "YES" << endl
#define NO()            cout << "NO" << endl
#define Yes()           cout << "Yes" << endl
#define No()            cout << "No" << endl
#define ceil(x, y)      ((x + y - 1) / (y))
#define debug(x)        cerr << #x << ": " << (x) << '\n'
#define debug2(x, y)    cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << '\n'
#define debug3(x, y, z) cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << ", " << #z << ": " << (z) << '\n'
#define dbg(v)          for (size_t _ = 0; _ < v.size(); ++_){ cerr << #v << "[" << _ << "] : " << v[_] << '\n'; }

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

const ll MOD = 1000000007; // 10^9 + 7
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

void solve() {
  ll N, K, R, S, P; cin >> N >> K >> R >> S >> P;
  string T; cin >> T;
  vector<string> t;

  for (int i = 0; i < K; i++) {
    string ti = "";
    for (int j = i; j < N; j += K) {
      ti += T[j];
    }
    t.push_back(ti);
  }

  int ans = 0;
  for (int i = 0; i < t.size(); i++) {
    int r = 0, s = 0, p = 0;
    if (t[i][0] == 'r') p += P;
    if (t[i][0] == 's') r += R;
    if (t[i][0] == 'p') s += S;

    int n = t[i].size();
    // debug2(t[i], n);
    for (int j = 1; j < n; j++) {
      int rr = max(s, p), ss = max(r, p), pp = max(r, s);

      if (t[i][j] == 'r') pp += P;
      if (t[i][j] == 's') rr += R;
      if (t[i][j] == 'p') ss += S;

      r = rr; s = ss; p = pp;
    }

    ans += max({r, s, p});
  }
  outl(ans);
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  srand((unsigned)time(NULL));
  fix(12);

  solve();
}


Measured memory_bytes: 4404
#include <bits/stdc++.h>
#define fastIO (cin.tie(0), cout.tie(0), ios::sync_with_stdio(false))
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define precise(i) fixed << setprecision(i)
using lint = long;
using llint = long long;
using namespace std;

int main() {
    fastIO;
    lint n, h, w;
    cin >> n >> h >> w;

    int cnt = 0;
    while (n--) {
        llint a, b;
        cin >> a >> b;
        if (a >= h && b >= w)
            cnt++;
    }
    cout << cnt << endl;
}


Measured memory_bytes: 3588
import numpy as np
N = int(input())
seq = list(map(int, input().split()))

M, m = max(seq), min(seq)
for i in range(N):
    if seq[i] == M:
        x = i
    if seq[i] == m:
        y = i

print(2 * N - 2)

if M + m >= 0:
    for i in range(N - 1):
        seq[i + 1] += M
        print(x + 1, i + 2)
        if seq[i + 1] > M:
            M = seq[i + 1]
            x = i + 1
        seq[i + 1] += M
        print(x + 1, i + 2)
        if seq[i + 1] > M:
            M = seq[i + 1]
            x = i + 1
else:
    for i in range(N - 1, 0, -1):
        seq[i - 1] += m
        print(y + 1, i)
        if seq[i - 1] < m:
            m = seq[i - 1]
            y = i - 1
        seq[i - 1] += m
        print(y + 1, i)
        if seq[i - 1] < m:
            m = seq[i - 1]
            y = i - 1

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

int main(){
  vector<int> a(3);
  for ( int i = 0; i < 3; ++i ) {
    cin >> a[i];
  }
  sort(a.begin(), a.end());
  int ans = a[2] - a[1] + (a[1] - a[0]);
  cout << ans <<  endl;
  return 0;
}

Measured memory_bytes: 256
import sys

N, K = map(int, input().split())
A = list(map(int, sys.stdin.readline().rsplit()))
B = [-1] * N

if K <= N:
    now = 0
    for i in range(K):
        now = A[now] - 1
    print(now + 1)
    exit()

now = 0
for i in range(N):
    if B[now] == -1:
        B[now] = i
        now = A[now] - 1
    else:
        tmp = (K - B[now]) % (i - B[now])
        for i in range(tmp):
            now = A[now] - 1
        print(now + 1)
        exit()


Measured memory_bytes: 31260
def prime(N):
    f = []
    c = 0
    r = int(N**0.5)
    for i in range(2, r+2):
        while N % i == 0:
            c+= 1
            N = N //i
        if c != 0:
            f.append((i,c))
            c = 0
    if N!=1:
        f.append((N,1))
    return f

def solve(N):
    import sys
    #print(N, file=sys.stderr)
    org = N
    A = []
    a = 0
    f = prime(N)
    for p, c in f:
        for i in range(1, c+1):
            z = p ** i
            if c > 0 and N >=z and N %z == 0:
                c -= i
                #print(N, p**i)
                N //= z
                A.append(z)
                a += 1
    return a, A

def primes():
    primes = [2]
    for i in range(3, 10**5+1, 2):
        if all(i % p != 0 for p in primes):
            primes.append(i)
    return primes

def test():
    def primes():
        with open("primes.txt", "r") as f:
            return [int(x) for x in f.readline().split()]
    primes = primes()
    for N in range(1, 10**5+1):
        org = N
        a0, A = solve(N)
        a1 = 0
        B = []
        for p in primes:
            for i in range(1, 10**16):
                z = p ** i
                if N < z:
                    break
                if N % z == 0:
                    N //= z
                    a1 += 1
                    B.append(z)
        if a0 != a1:
            print("NG on", org, "actual=%d"%a0, A, "expect=%d"%a1, B)
            break
#print("solve(36)",prime(36), solve(36))
#test()
N = int(input())
print(solve(N)[0])


Measured memory_bytes: 9572
#include<bits/stdc++.h>
using namespace std;
#define all(a)  (a).begin(),(a).end()
typedef long long ll;
const ll mod=1000000007;
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)

int main() {
  int n,m; cin >>n >>m;
  vector<int> used(n,-1);
  bool valid = true;
  for(int i=0;i<m;++i){
    int s,c;cin >> s>>c;
    if(used[s-1]>=0&&used[s-1]!=c){
      valid = false;
      break;
    }
    if(s==1&&c==0&&n>1){
      valid = false;
      break;
    }
    used[s-1] = c;
  }
  int out = -1;
  if(valid){
    out = 0;
    for(int i=0;i<n;++i){
      out *=10;
      int c = used[i];
      if(c<0){
        c = 0;
        if(i==0&&n>1) c=1;
      }
      out += c;
    }
  }
cout << out << endl;
  return 0;
}


Measured memory_bytes: 256
Seg = [
  0b0111111,
  0b0000110,
  0b1011011,
  0b1001111,
  0b1100110,
  0b1101101,
  0b1111101,
  0b0100111,
  0b1111111,
  0b1101111
]

while (n = $stdin.gets.to_i) != -1 do
  prev = 0b0000000
  n.times do
    nextNumber = Seg[$stdin.gets.to_i]
    tmp = (prev ^ nextNumber).to_s(2)
    puts ("0" * (7 - tmp.length) + tmp)
    prev = nextNumber
  end
end

Measured memory_bytes: 6096
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,m,d = na()

a = 1 if d == 0 else 2
print(a*(m-1)*(n-d)/(n**2))

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

using namespace std;

#define ll  long long
#define ld  double

#define sz(x)   (int)x.size()
#define all(x)  x.begin(),x.end()

#define pb  emplace_back
#define X   first
#define Y   second

const int   N   = 1e7 + 5;
const int   mod = 998244353;

void add(int &a,int b)  {
    a += b;
    if (a >= mod)
        a -= mod;
}
void sub(int &a,int b)  {
    a -= b;
    if (a <  0)
        a += mod;
}
int mul(int a,int b)    {
    return  1ll * a * b % mod;
}
int inv(int a,int p)    {
    return  a == 1 ? 1 : p - 1ll * p * inv(p % a,a) / a;
}

int Fac[N];
int Inv[N];
int Pow[N];

int Ckn(int n,int k)    {
    if (n < k)  return  0;
    if (k < 0)  return  0;

    return  mul(Fac[n],mul(Inv[k],Inv[n - k]));
}

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    Fac[0] = Inv[0] = 1;

    for(int i = 1 ; i < N ; ++i)    Fac[i] = mul(Fac[i - 1],i);     Inv[N - 1] = inv(Fac[N - 1],mod);
    for(int i = N - 2 ; i ; --i)    Inv[i] = mul(Inv[i + 1],i + 1);

    int n;  cin >> n;

    int ans = Pow[0] = 1;

    for(int i = 1 ; i <= n ; ++i)   {
        ans = mul(ans,3);
        Pow[i] = mul(Pow[i - 1],2);
    }

    for(int i = n / 2 + 1 ; i <= n ; ++i)
        sub(ans,mul(Ckn(n,i),Pow[n - i + 1]));

    cout << ans << endl;
}

Measured memory_bytes: 117504
// class point	の練習（クラスの高度な実装）
#include <iostream>
#include <iomanip>
#include <cstring>
#define INF 1000001
typedef long long llong;
using namespace std;



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


	for (int i = 1; i <= n; i++) {
		if (i % 3 == 0)cout << " " << i;
		else {
			int x = i;
			while (x > 0) {
				if (x % 10 == 3) {
					cout << " " << i;
					break;
				}
				else x /= 10;
			}

		}
	}


	cout << endl;


	return 0;
}



Measured memory_bytes: 3108
n, m = gets.split.map(&:to_i)
d = gets.split.map(&:to_i)
dp = Array.new(n+1,n)
dp[0] = 0
for i in 0..n
    m.times do |j|
        if n >= d[j]
            dp[i] = [dp[i],dp[i-d[j]]+1].min
        end
    end
end
puts dp[n]

Measured memory_bytes: 6500
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define FOR(n) for(int i=0;i<n;i++)
#define FORJ(n) for(int j=0;j<n;j++)
#define PRN(n) printf("%d\n",n)
#define PRF(n) printf("%lf\n",n)
#define PRL(n) printf("%lld\n",n)
#define PRS(s) printf("%s\n",s)
#define PRC(c) printf("%c",c)
#define INF 10000000000
#define mod 1000000007
#define X 1000000
typedef long long int ll;
ll finv[X];
ll fac[X];
ll inv[X];
ll usort(const void *a, const void *b){return *(ll*)a-*(ll*)b;}
ll dsort(const void *a, const void *b){return *(ll*)b-*(ll*)a;}
ll ssort(const void *a, const void *b){return strcmp((char*)a,(char*)b);}
ll min(ll a,ll b){
  if(a>b)return b;
  return a;
}
ll max(ll a,ll b){
  if(a>b)return a;
  return b;
}
ll z(ll a){return max(a,-a);}
ll gcd(ll a,ll b){if(!b){return a;}else{return gcd(b,a%b);}}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
ll kt(ll a){
  ll sum=0;
  while(a){
    a/=10;
    sum++;
  }
  return sum;
}
ll ks(ll a){
  ll sum=0;
  while(a){
    sum+=a%10;
    a/=10;
  }
  return sum;
}
void ppp(){
  fac[0]=fac[1]=1;
  finv[0]=finv[1]=1;
  inv[1]=1;
  for (int i=2;i<X;i++){
    fac[i]=fac[i-1]*i%mod;
    inv[i]=mod-inv[mod%i]*(mod/i)%mod;
    finv[i]=finv[i-1]*inv[i]%mod;
  }
}
ll nCr(int n,int k){
  return fac[n]*(finv[k]*finv[n-k]%mod)%mod;
}
int main(void){
  ll a,b,k;
  scanf("%lld %lld %lld",&a,&b,&k);
  ll x=min(a,k);
  a-=x;
  k-=x;
  b-=min(b,k);
  printf("%lld %lld\n",a,b);
  return 0;
}


Measured memory_bytes: 128
use std::io::{self, BufRead};

fn main() {
    let stdin = io::stdin();
    let mut lines = stdin.lock().lines();
    let n = lines.next().unwrap().unwrap().parse::<usize>().unwrap();
    let s_t = lines.next().unwrap().unwrap();
    let mut s_t = s_t.split_whitespace();
    let s = s_t.next().unwrap().chars().collect::<Vec<char>>();
    let t = s_t.next().unwrap().chars().collect::<Vec<char>>();

    let mut ans = String::new();
    for i in 0..n {
        ans.push(s[i]);
        ans.push(t[i]);
    }

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


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

using namespace std ;

#define IOS ios::sync_with_stdio(0); cin.tie(0), cout.tie(0)
#define ll long long int 

#define fr first
#define se second

#define all(v) v.begin(),v.end() 
#define rall(v) v.rbegin(),v.rend()
#define sz(v) v.size() 

#define pb push_back
#define mp make_pair 

#define PI 3.141592653589793238



ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b) {return a*b / gcd(a,b) ;}


//bool valid(int x, int y){return x > 0 && x < n && y > 0 && y < m;}

int n, m, a[33], cntr;

int main(){
  cin >> n >> m;
  for(int i = 0 ; i < n ; i++){
    int k;
    cin >> k;
    for(int i = 0 ; i < k ; i++){
      int l;
      cin >> l;
      a[l]++;
    }
  }
  for(int i = 1 ; i <= m ; i++)
    if(a[i] == n)
      cntr++;
  cout << cntr;
  return 0;
}


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

int main() {
    int k, a, b;
    cin >> k >> a >> b;
    bool f = false;
    for(int i = 1; i <= 1000; ++i) {
        if(i*k >= a && i*k <= b) {
            f = true;
            break;
        }
    }
    if(f) {
        cout << "OK" << '\n';
    } else {
        cout << "NG" << '\n';
    }

    return 0;
}


Measured memory_bytes: 3636
import java.io.BufferedReader;
import java.io.InputStreamReader;



@SuppressWarnings({"javadoc"})
public class Main
{

  public static void main
  (
    String[] args
  )
  {
    BufferedReader in_stream;

    String        in_T;

    int  cnt;
    int  num;
    char before;
    char now;

    StringBuilder ans;

    try
    {
      in_stream = new BufferedReader(new InputStreamReader(System.in));

      /*----------------
       * 引数
       *----------------*/
      in_T = new String(in_stream.readLine());


      /*----------------
       * 計算
       *----------------*/
      num = in_T.length();
      ans = new StringBuilder();

      /* 1文字目 */
      before = in_T.charAt(0);
      if('?' == before)
      {
        if( (1 == num) || ('P' == in_T.charAt(1)) )
        {
          before = 'D';
        }
        else
        {
          before = 'P';
        }
      }
      ans.append(before);

      /* 2文字目以降 */
      for(cnt=1; cnt<num; cnt++)
      {
        now = in_T.charAt(cnt);

        if('?' == now)
        {
          if('P' == before)
          {
            before = 'D';
          }
          else
          {
            if( (cnt == (num-1)) || ('P' == in_T.charAt(cnt+1)) )
            {
              before = 'D';
            }
            else
            {
              before = 'P';
            }
          }
        }
        else
        {
          before = now;
        }

        ans.append(before);
      }

      System.out.println( ans.toString() );
    }
    catch(Exception e)
    {
      e.printStackTrace();
    }
  }



}





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



int main(void){
  string S;
  cin >> S;
  int ans = 1;
  for(int i = 0; i < 4; i++){
    int samecount = 0;
    for(int j = 0; j < 4; j++){
      if(S.at(i) == S.at(j))
      samecount++;
    }
    if(samecount != 2){
      ans = 0;
      break;
    }
  }
  if(ans){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}


Measured memory_bytes: 256
from fractions import gcd

t = int(input())
abcdt = [list(map(int, input().split())) for _ in range(t)]

for a, b, c, d in abcdt:
  if a < b:
    print('No')
  elif d < b:
    print('No')
  else:
    if d - b != 0:
      g = gcd(b, d - b)
    else:
      g = b
    if (a - c - 1) // g >= - ((-(a - b + 1)) // g):
      print('No')
    else:
      print('Yes')

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

using namespace std;

typedef vector<int> vi;
typedef vi::iterator vitr;

int main()
{
    int n, m;
    vi d, t;
    cin >> n;
    d.resize(n);
    for(int i=0; i<n; i++) cin >> d[i];
    cin >> m;
    t.resize(m);
    for(int i=0; i<m; i++) cin >> t[i];
    sort(d.begin(), d.end());
    sort(t.begin(), t.end());
    
    vitr p = d.begin(), q = t.begin();
    
    while(q!=t.end())
    {
        while(p!=d.end() && *p<*q) p++;
        if(p==d.end() || *p>*q)
        {
            cout << "NO" << endl;
            return 0;
        }
        p++;
        q++;
    }
    cout << "YES" << endl;
    
    return 0;
}


Measured memory_bytes: 1792
N, M = map(int, input().split())

lps = list()

for i in range(M):
    p, s = input().split()
    lps.append([int(p), s])
#print(lps)

lcor = [0] * N
lwrg = [0] * N
for i in range(M):
    if lps[i][1] == "AC":
        if lcor[lps[i][0]-1] == 0:
            lcor[lps[i][0]-1] += 1
    elif lps[i][1] == "WA":
        if lcor[lps[i][0]-1] == 0:
            lwrg[lps[i][0]-1] += 1

for i in range(N):
    if lcor[i] == 0:
        lwrg[i] = 0

print(sum(lcor), sum(lwrg))

Measured memory_bytes: 23556
"""
Aさん：身長Ha , パワーPa
Bさん：身長Hb , パワーPb
二人どちらも積めるのに順番を間違えたばかりに一人しか積めない、という事態を避けたい。
Aさんが先に積むべき？Bさんが先に積むべき？
Aさん、Bさんの手前までの時点で高さSまで積みあがっているとする。S <= min(Hb,Ha)とする。

S+Pa > Hb　かつ S+Pb <= HaならBが先
S+Pb > Ha　かつ S+Pa <= HbならAが先

Pa-Hb > Pb-Ha ならBが先でAが後
書き換えるとPa+Ha > Pb+HbならBが先でAが後
つまり、P+H順にソートしてナップサックすればよい
"""


N = int(input())
HP = [list(map(int,input().split())) for _ in range(N)]
HP.sort(key = lambda x:x[0]+x[1])
#dp[i][j] -> j人積む場合の座布団の最小枚数
dp = [float("INF")]*(N+1)
dp[0] = 0
for h,p in HP:
    for j in range(N,0,-1):
        if dp[j-1] <= h:
            dp[j] = min(dp[j],dp[j-1]+p)

for j in range(N,-1,-1):
    if dp[j] != float("INF"):
        print(j)
        break

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

int n,m;
int a[2001];

int main(void){
	while(1){
		scanf("%d%d",&n,&m);
		if(n==0 && m==0)break;
		int res=0;
		for(int i=0;i<n;i++){
			scanf("%d",&a[i]);
		}
		for(int i=0;i<n;i++){
			for(int j=i+1;j<n;j++){
				if(a[i]+a[j]<=m){
					res=max(res,a[i]+a[j]);
				}
			}
		}
		if(res==0)printf("NONE\n");
		else printf("%d\n",res);
	}
	return 0;
}

Measured memory_bytes: 3236
import java.util.*;

public class Main {

    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        int min = a[0];
        int max = a[0];
        for (int i = 0; i < n; i++) {
            min = Math.min(a[i], min);
            max = Math.max(a[i], max);
        }
        System.out.println(max - min);
    }

}


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

/*
sort(sp.begin(), sp.end(), [](PAIR l, PAIR r){
        return l.first<r.first || (l.first==r.first && l.second > r.second);
        });
*/

typedef long long ll;

#define fi first
#define se second

int main()
{
    double pi = 3.14159265358;
    int a, b, h, m;
    cin >> a >> b >> h >> m;
    double deg = 2 * pi * abs(30 * h - 5.5 * m) / 360.0;
    cout << setprecision(12) << sqrt(a * a + b * b - 2 * a * b * cos(deg)) << endl;

    return 0;
}

Measured memory_bytes: 4228
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#define ll long long
#define ld long double
#define mk make_pair
#define fi first
#define se second
#define vll vector<ll>
#define pii pair<ll,ll>
#define vvll vector< vector<ll> >
#define pb push_back
#define sz(v) (v).size()
#define inf 1e18
#define md 1000000007
#define all(v) (v).begin(),(v).end()
#define rep(i,a,b) for(ll i=a;i<b;++i)
#define tel(a){cout<<a<<"\n";}
#define tell(a,b){cout<<a<<" | "<<b<<"\n";}
#define telll(a,b,c){cout<<a<<" | "<<b<<" | "<<c<<"\n";}
#define teln(v,n){cout<<"v- ";rep(i,0,n)cout<<v[i]<<" ";cout<<"\n";}
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); 
 
using namespace std;
using namespace __gnu_pbds;
 
// template<typename T>
using o_set=tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update>;
 
#define M 1000010



int main(){
	IOS;
	ll h,w,n;cin>>h>>w>>n;
	ll ans=max(h,w);
	if(n%ans==0)ans=n/ans;
	else ans=n/ans+1;
	cout<<ans;
	
	
	return 0;
}

Measured memory_bytes: 256
// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
//#define int ll
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
#define mt make_tuple
typedef tuple<int,int,int> tp;
typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
//template<class C>constexpr int size(const C &c){return (int)c.size();}
//template<class T,size_t N> constexpr int size(const T (&xs)[N])noexcept{return (int)N;}
const double PI=acos(-1);
const double EPS=1e-7;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9+10;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int main(){
	string s;
	cin>>s;
	if(s.size()==26){
		for(int i=25;i>=0;i--){
			char c=127;
			for(int j=i+1;j<s.size();j++)if(s[i]<s[j])
				c=min(c,s[j]);
			if(c!=127){
				cout<<s.substr(0,i)<<(char)c<<endl;
				return 0;
			}
		}
		cout<<-1<<endl;
	}else{
		rep(i,26){
			bool h=true;
			rep(j,s.size())if(s[j]==i+'a')h=false;
			if(h){
				cout<<s<<(char)(i+'a')<<endl;
				return 0;
			}
		}
	}
}





Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<utility>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<bitset>
#include<iomanip>
#include<list>
#include<deque>
using namespace std;
//#define MODE 1
#ifdef MODE
#define DEB(X) cout<< #X <<": "<<X<<" ";
#define DEB2(X) cout<<X<<" ";
#define END cout<<endl;
#else
#define DEB(X) {}
#define DEB2(X) {}
#define END {}
#endif
typedef long long ll;
#define int ll
#define uset unordered_set
#define umap unordered_map
//typedef std::pair<int,int> P;
struct edge{int to,cost;};
const int INF=100000000000000000;
const int INF2=9223372036854775807;
const int MOD=1000000007;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define min(X,Y) (((int)(X)<(int)(Y))?(X):(Y))
#define max(X,Y) (((int)(X)>(int)(Y))?(X):(Y))
#define NP(X,Y) next_permutation(X,Y)
#define setdouble(X,Y) cout<<fixed<<setprecision(X)<<Y
int ceil2(int a,int b){if(a%b==0){return a/b;}else{return a/b+1;}}
int pow2(int a,int b){int r=1;for(int i=1;i<=b;i++){r*=a;}return r;}
int Log2(int a){int t=0;while(1){if(a==0||a==1){break;}a/=2;t++;}return t;}

int A;

signed main(){
	cin>>A;
	cout<<A+A*A+A*A*A<<endl;
	return 0;
}


Measured memory_bytes: 3632
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

  public static void main(String[] args) throws FileNotFoundException {

//    Scanner cin = new Scanner(new FileReader("input.txt"));
    Scanner cin = new Scanner(System.in);

    int num = cin.nextInt();
    int[] target = new int[3];
    target[0] = cin.nextInt();
    target[1] = cin.nextInt();
    target[2] = cin.nextInt();

    int[] bamboo = new int[num];
    for (int i = 0; i < num; i++) {
      bamboo[i] = cin.nextInt();
    }
    //System.out.println(Arrays.toString(bamboo));

    int res = findMin(target, bamboo, 0, 0, 0, 0, num);
    System.out.println(res);

  }

  //
  public static int findMin(int[] target, int[] bamboo, int bA, int bB, int bC, int use, int used) {

    if (use == used) {
      //if (Math.min(bA, Math.min(bB, bC)) > 0) {
      if (bA > 0 && bB > 0 && bC > 0) {
        return Math.abs(bA - target[0]) + Math.abs(bB - target[1]) + Math.abs(bC - target[2]) - 30;
      } else {
        return Integer.MAX_VALUE / 2;
      }
    } else {
      int res1 = findMin(target, bamboo, bA, bB, bC, use + 1, used);
      int res2 = findMin(target, bamboo, bA + bamboo[use], bB, bC, use + 1, used) + 10;
      int res3 = findMin(target, bamboo, bA, bB + bamboo[use], bC, use + 1, used) + 10;
      int res4 = findMin(target, bamboo, bA, bB, bC + bamboo[use], use + 1, used) + 10;
      return Math.min(res1, Math.min(res2, Math.min(res3, res4)));
    }

  }

}

Measured memory_bytes: 22996