akhauriyash/Code-Regression huggingface dataset:
// SeeAlso: 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define MAX 100000
#define NIL -1
#define MOD 1000000007

typedef int _loop_int;
#define rep(i,n) for(int i = 0; i < n; i++)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define debug(x) cout<<#x<<": "<<x<<endl
#define debig_vec(v) cout<<#v<<":";rep(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

// 最大公約数
inline constexpr ll gcd(ll a,ll b){if(!a||!b)return 0;while(b){ll c=b;b=a%b;a=c;}return a;}
// 最小公倍数
inline constexpr ll lcm(ll a,ll b){if(!a||!b)return 0;return a*b/gcd(a,b);}

#define print2D(h, w, arr) rep(i, h) { rep(j, w) cout << arr[i][j] << " "; cout << endl; }
template<class T> inline void print(const T& x){cout << setprecision(12) << x << endl;}
template<class T, class... A> inline void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

const long long INF = 1LL<<60;

char henkan(ll t) {
    switch (t) {
    case 1:
        return 'a';
    case 2:
        return 'b';
    case 3:
        return 'c';
    case 4:
        return 'd';
    case 5:
        return 'e';
    case 6:
        return 'f';
    case 7:
        return 'g';
    case 8:
        return 'h';
    case 9:
        return 'i';
    case 10:
        return 'j';
    case 11:
        return 'k';
    case 12:
        return 'l';
    case 13:
        return 'm';
    case 14:
        return 'n';
    case 15:
        return 'o';
    case 16:
        return 'p';
    case 17:
        return 'q';
    case 18:
        return 'r';
    case 19:
        return 's';
    case 20:
        return 't';
    case 21:
        return 'u';
    case 22:
        return 'v';
    case 23:
        return 'w';
    case 24:
        return 'x';
    case 25:
        return 'y';
    case 0:
        return 'z';
    default:
        return 'a';
    }
    return 'a';
}

int main() {
    ll n; cin >> n;
    string s;


    while (n > 0) {
        ll memo = n % 26;
        if (memo == 0) {
            s += 'z';
            n = (n / 26) - 1;
        } else {
            s += (char) ((memo - 1) + 'a');
            n = n / 26;
        }
    }

    reverse(s.begin(), s.end());
    print(s);
    return 0;
}


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

const int N = 100 * 1000 + 10;

int n, ans = 1;
int arr[N];

void input() {
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    return;
}

void solve() {
    char ch = '?';
    for (int i = 0; i < n - 1; i++) {
        if (ch == '?') {
            if (arr[i + 1] > arr[i])
                ch = '<';
            else if (arr[i + 1] < arr[i])
                ch = '>';
        }

        else if (arr[i + 1] > arr[i] && ch == '>') {
            ans++;
            ch = '?';
        }
        else if (arr[i + 1] < arr[i] && ch == '<') {
            ans++;
            //cerr << "!!! " << i << endl;
            ch = '?';
        }
        //cerr << i << " :: " << ch << endl;
    }
    return;
}

int main() {
    input() ;
    solve() ;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 640
h,w,k=map(int,input().split())
A=[]
for i in range(h):
    a=input()
    A.append([ a[i]=="#" for i in range(w)])
# print(A)
ans=0

for bit in range(1<<h):
    for tib in range(1<<w):
        now=0
        for i in range(h):
            for j in range(w):
                if (bit>>i) &1==0 and (tib>>j)&1==0 and A[i][j]==1: now+=1
        if now==k : ans+=1
print(ans)

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

#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());


void c_p_c()
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#endif
}
int solve(int x)
{
  int ans = 0;
  while(x%2 == 0)
  {
    ans++;
    x/=2;
  }
  return ans;
}
int32_t main()
{
  //c_p_c();
  int n;
  cin >> n;
  int a[n];
  int e = 0;
  for(int i=0;i<n;i++)
  {
    cin >> a[i];
    if(a[i]%2 == 0)
    {
      e++;
    }
  }
  if(e == 0)
  {
    cout<<e<<endl;
  }
  else
  {
    int res = 0;
    for(int i=0;i<n;i++)
    {
      if(a[i]&1) continue;
      res += solve(a[i]);
    }
    cout<<res<<endl;
  }

  return 0;
}



Measured memory_bytes: 384
fun main(args: Array<String>){
    val str = readLine()!!
    for(i in str.indices){
        var cnt = 0
        for(j in str.indices){
            if(str[i] == str[j]){
                cnt++
            }
        }
        if(cnt % 2 != 0){
            println("No")
            return
        }
    }
    println("Yes")
}

Measured memory_bytes: 33720
#include <bits/stdc++.h>
//#pragma GCC optimize(2)
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
#define rep(i,a,b) for(int i = (a);i <= (b);i++)
#define pii pair<int,int>
#define pll pair<long long, long long>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1e9 + 7;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const int maxn = 2e5 + 5;
const double eps = 1e-8;
const double pi = acos(-1.0);
ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);}
ll lcm(ll a,ll b){return a * b / gcd(a,b);}
ll poww(ll x,ll y,ll p){ll ans = 1;while(y){if(y & 1) ans = ans * x % p;x = x * x % p;y >>= 1;}return ans % p;}
bool isp(ll x){if(x < 2) return 0; for(ll i = 2;i * i <= x;i++){if(x % i == 0) return 0;}return 1;}
int n,x;
pii a[maxn];
void solve(){
	sort(a+1,a+n+1);
	rep(i,1,n) cout << a[i].se << " ";
	cout << endl;
}
int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n;
	rep(i,1,n){
		cin >> x;
		a[i] = mp(x,i);
	}
	solve();
	return 0;
}
//do smt instead of nothing! never give up!

Measured memory_bytes: 1664
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	int q[50],p[50],n; cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> p[i];
		q[i] = p[i];
	}
	sort(q, q + n);
	int cnt = 0;
	for (int i = 0; i < n; ++i)
		if (p[i] != q[i]) ++cnt;
	if (cnt <= 2) cout << "YES" << endl;
	else cout << "NO" << endl;
	return 0;
}

Measured memory_bytes: 256
def main():
    n, nn, nnn = map(int, input().split(' '))
    print('Yes' if n + nn >= nnn else 'No')


def main_b():
    t = int(input())
    ad = [input() for i in range(t)]
    t = int(input())
    mo = [input() for i in range(t)]

    from collections import Counter
    ad = dict(Counter(ad))
    mo = dict(Counter(mo))
    ans = 0
    for a in ad:
        tmp = ad.get(a, 0) - mo.get(a, 0)
        if ans < tmp:
            ans = tmp
    print(ans)
if __name__ == '__main__':
    main_b()

Measured memory_bytes: 3316
#include <iostream>
#include <cstring> // memset

using namespace std;

bool G[50][50] = {{false}};
bool visited[50] = {false};

void DFS(int u, int N) {
  visited[u] = true;

  for (int v = 0; v < N; ++v) {
    if (!G[u][v]) continue;
    if (visited[v]) continue;
    DFS(v, N);
  }
}

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

  int N, M;
  cin >> N >> M;
  int a, b;

  for (int i = 0; i < M; ++i) {
    cin >> a >> b;
    --a;
    --b;
    G[a][b] = G[b][a] = true;
  }

  int ans = 0;
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
      if (!G[i][j]) continue;
      G[i][j] = false;
      DFS(0, N);
      bool has_bridge = false;
      for (int v = 0; v < N; ++v) {
        if (!visited[v]) {
          has_bridge = true;
          break;
        }
      }
      if (has_bridge) ++ans;
      G[i][j] = true;
      memset(visited, false, N);
    }
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
#define rep(i,n) for(ll i=0;i<n;++i)
#define all_map(itr,mp) for(auto itr=mp.begin();itr!=mp.end();itr++)
#define ALL(a) (a).begin(),(a).end()

using namespace std;
using ll  = long long;
using pll = pair<ll, ll>;

const ll MOD  = 1e9 + 7;
const ll LINF = 1LL << 62;
const int INF = 1e9 + 7;

int main(){
    ll k;
    cin >> k;

    ll m = 10;

    if(k % 7 == 0)k /= 7;
    ll base = 9*k;

    rep(i, 10000000){
        m %= 9*k;
        if(m == 1){
            cout << i+1 << endl;
            return 0;
        }
        m *= 10;
    }

    cout << -1 << endl;
}


Measured memory_bytes: 3576
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repi(i, s, n) for (int i = (s); i < (n); i++)
#ifdef LOCAL
#define INPUT_FILE                   \
  ifstream in("abc148/abc148_c.txt"); \
  cin.rdbuf(in.rdbuf());
#else
#define INPUT_FILE
#endif
#define CIN_OPTIMIZE \
  cin.tie(0);        \
  ios::sync_with_stdio(false);
typedef pair<int, int> P;
typedef long long ll;
const int INF = 100100100;
const int MOD = 1e9 + 7;

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() {
  INPUT_FILE CIN_OPTIMIZE;

  int a, b;
  cin >> a >> b;

  cout << lcm(a, b) << endl;
}

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

using namespace std;

long long N, a[200005];
long long mini = ~0ull >> 1;

int main() {
    scanf("%lld", &N);
    for (int i = 0; i != N; ++i) scanf("%lld", &a[i]);
    for (int i = 1; i != N; ++i) a[i] += a[i - 1];
    for (int i = 0; i != N - 1; ++i) mini = min(mini, abs(2 * a[i] - a[N - 1]));
    printf("%lld\n", mini);
    return 0;
}

Measured memory_bytes: 1664
#include<bits/stdc++.h>
#include<string>
using namespace std;
string a, b;
int main(){
  cin >> a >> b;
  int asize = a.size();
  int bsize = b.size();
  if(asize > bsize) cout << "GREATER" << endl;
  else if(asize < bsize) cout << "LESS" << endl;
  else if(a > b) cout << "GREATER" << endl;
  else if(a < b) cout << "LESS" << endl;
  else if(a == b) cout << "EQUAL" << endl;
}

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


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

	vector<int> A(N), B(M);

	for(int i = 0; i < N; i++) {
		cin >> A[i];
	}

	for(int i = 0; i < M; i++) {
		cin >> B[i];
	}

	vector<int> votes(N);

	for(int i = 0; i < M; i++) {
		for(int j = 0; j < N; j++) {
			if(A[j] <= B[i]) {
				votes[j]++;
				break;
			}
		}
	}

	int p = 0, best = -1;
	for(int i = 0; i < N; i++) {
		if(best < votes[i]) {
			best = votes[i];
			p = i;
		}
	}

	cout << p+1 << endl;
}

Measured memory_bytes: 1204
#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() {
  string s;
  cin >> s;
  int n = s.size();

  vector<int> res(n, 0);
  int r = 0;
  rep(i, n) {
    if (s[i] == 'R') ++r;
    else {
      res[i] += r / 2;
      res[i-1] += r - r / 2;
      r = 0;
    }
  }
  int l = 0;
  for (int i = n-1; i >= 0; --i) {
    if (s[i] == 'L') ++l;
    else {
      res[i] += l / 2;
      res[i+1] += l - l / 2;
      l = 0;
    }
  }
  rep(i, n-1) printf("%d ", res[i]);
  printf("%d\n", res[n-1]);
  return 0;
}

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

using namespace std;
typedef long long ll;

#define N 100005
int v[N];

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

int main(){

    int n, k;
    scanf ("%d %d", &n, &k);
    int g = 0;
    for (int i = 0; i < n; i++){
        scanf ("%d", v + i);
        g = gcd(v[i], g);
    }

    for (int i = 0; i < n; i++){
        if (v[i] >= k && (v[i] - k) % g == 0){
            printf ("POSSIBLE\n");
            return 0;

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


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1LL << 60;

int calc_digit(long long N){
    int res = 0;
    while(N > 0){
        res++;
        N /= 10;
    }
    return res;
}

int main(){
    long long N; cin >> N;
    long long res = INF;
    for(long long a = 1; a*a<= N ; a++){
        if(N%a!=0)continue;
        long long b = N/a;
        long long tmp = max(calc_digit(a),calc_digit(b));
        res = min(res,tmp);
    }
    cout << res << endl;
}

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

//#define int long long
#define endl "\n"
#define REP(i,a,n) for(int i=a;i<n;++i)
#define REPR(i,a,n) for(int i=a;i>n;--i)
#define RUP(a,b) ((a+b-1)/(b))
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define mt make_tuple

typedef long long ll;
typedef pair<int,int> Pii;
typedef tuple<int,int,int> Tiii;
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef vector<Pii> VPii;
typedef vector<string> Vs;

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;}
template<class T> void YesNo(T a) {cout<<(a?"Yes":"No")<<endl;}
template<class T> void YESNO(T a) {cout<<(a?"YES":"NO")<<endl;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
void uniq(Vi &v){sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());}
const int MOD=1000000007;
//const int INF=LLONG_MAX/2;

signed main() {cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
    int n,count=0;
    cin>>n;
    Vi a(n);
    REP(i,0,n) cin>>a[i];
    
    multiset<int> ans;
    REP(i,0,n){
        auto it=ans.lower_bound(a[i]);
        if(it==ans.begin()){
            ans.insert(a[i]);
        }else{
            it--;
            ans.erase(it);
            ans.insert(a[i]);
        }
    }
    cout<<ans.size()+count<<endl;
    return 0;
}


Measured memory_bytes: 5376
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        
        Scanner sc = new Scanner(System.in);
        String S = sc.next();
        
        int ans = 0;
        int len = 0;
        for(int i = 0; i  < S.length(); i++){
            char x = S.charAt(i);
            
            switch(x){
                case 'A' :
                case 'C' :
                case 'G' :
                case 'T' :
                    len++;
                    break;                    
                default :
                    len = 0;
                    break;
            }
            
            ans = Math.max(ans, len);
        }
        
        System.out.println(ans);
    }
}


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

using namespace std;

int main() {
  string n;
  cin >> n;
  for (char& c : n) {
    if (c == '1') {
      c = '9';
    } else {
      c = '1';
    }
  }
  cout << n << endl;
  
  return 0;
}


Measured memory_bytes: 3604
import java.util.*;

public class Main {

  public static void main (String[] args) {

    Scanner sc = new Scanner(System.in);

    int N = sc.nextInt();
    int[] d = new int[N];

    for (int i = 0; i < N; i++) {
      d[i] = sc.nextInt();
    }

    sc.close();

    Arrays.sort(d);

    int w = d[N-1];
    int count = 1;

    for (int i = N-2; 0 <= i; i--) {
      if (d[i] < w) {
        w = d[i];
        count++;
      }
    }

    System.out.println(count);

  }

}

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

const llong MOD = 1e9+7;
const llong inf = 1<<30;

llong N;
vector<string> s;
vector<llong> stair;

void make_stair(void) {
    stair.resize(N+1);
    stair[0] = 0;
    for (int i = 1; i <= N; i++) stair[i] = stair[i-1]+i;
}

int main() {
    cin >> N; s.resize(N);
    make_stair();
    rep(i,N) cin >> s[i];
    rep(i,N) sort(s[i].begin(), s[i].end());
    sort(s.begin(), s.end());
    llong res = 0;
    int c = 1;
    rep(i,N-1) {
        if (s[i] == s[i+1]) {
            c++;
        }else{
            res += stair[max(c-1, 0)];
            c = 1;
        }
    }
    res += stair[max(c-1, 0)];
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 8064
#include<bits/stdc++.h>
#define dd double
#define ll long long

using namespace std;

int main()
{
    ll q;
    cin >> q;
    vector <ll> A;
    while(q--){
    ll qq,x;
    cin >> qq;
    if(qq==0){
        cin >> x;
        A.push_back(x);
    }
    if(qq==1){
        cin >> x;
        cout << A[x] << endl;
    }
    if(qq==2){
        A.pop_back();
    }
    }

    return 0;
}




Measured memory_bytes: 4904
import math, sys

n = int(input())
s = int(input())

def f(b, n):
    if n < b:
        return n
    else:
        return f(b, math.floor(n/b)) + n % b

if s == n:
    print(n+1)
    sys.exit()

#print(2, math.ceil(math.sqrt(n)))
for b in range(2, math.floor(math.sqrt(n))+1):
    #print(b)
    if(f(b, n) == s):
        print(b)
        sys.exit()

#print(math.floor(math.sqrt(n))-1)
for p in range(1, math.floor(math.sqrt(n))+1):
    #print(p)
    _p = math.floor(math.sqrt(n))+1-p
    b = int((n-s)/_p) + 1
    if(b >= 2 and f(b, n) == s):
        print(b)
        sys.exit()

print("-1")

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

int main() {
  int r,D,x;
  cin >> r >> D >> x;
  vector<int> X(10);
  X.at(0)=r*x-D;
  for(int i=1;i<10;i++){
    X.at(i)=r*X.at(i-1)-D;
  }
  for(int i=0;i<10;i++){
    cout << X.at(i) << endl;
  }
}


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

#define int long long
//#define uint __int128_t

#define pb push_back
#define fi first
#define se second
#define rep(i,s,n) for(int i = s;i<n;i++)
#define repe(i,s,n) for(int i = s;i<=n;i++)
#define rrep(i,s,n) for(int i = (n)-1;i>=(s);i--)
#define all(v) (v).begin(),(v).end()
#define chmin(a,b) a=min((a),(b))
#define chmax(a,b) a=max((a),(b))
#define low(a,b) lower_bound(all(a),(b))-(a).begin()
#define upp(a,b) upper_bound(all(a),(b))-(a).begin()
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0)
typedef long long ll;
typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<vint> vvint;
typedef vector<pint>vpint;
typedef pair<pint,int> P1;
typedef pair<int,pint> P2;
typedef pair<pint,pint> PP;
static const ll maxLL = (ll)1 << 62;
const ll MOD=1000000007;
const ll INF=1e18;

int N;
int dp[200020][2];
vint g[200020];

void dfs(int v,int p){
    int cnt=0;
    for(int e:g[v]){
        if(e==p)continue;
        dfs(e,v);
        cnt++;
    }
    if(cnt==0){
        dp[v][0]=dp[v][1]=1;
        return ;
    }
    dp[v][0]=dp[v][1]=1;
    for(int e:g[v]){
        if(e==p)continue;
        (dp[v][0]*=dp[e][1])%=MOD;
        (dp[v][1]*=(dp[e][0]+dp[e][1]))%=MOD;
    }
}

signed main() {
    IOS();
    //(1ll<<N)シフト演算のオーバーフローに気をつける
    cin>>N;
    rep(i,0,N-1){
        int a,b;
        cin>>a>>b;
        a--;b--;
        g[a].pb(b);
        g[b].pb(a);
    }
    dfs(0,-1);
    cout<<(dp[0][0]+dp[0][1])%MOD<<endl;
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    return 0;
}


Measured memory_bytes: 16640
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
long int idx[100001];
long long int power(long long int x,long long int y,long long int z)
{
    long long int res=1;
    x%=z;
    while(y>0)
    {
        if(y&1)
        res=(res*x)%z;
        x=(x*x)%z;
        y/=2;
    }
    return res;
}

long long int power1(long long int x,long long int y)
{
    long long int res=1;
    while(y>0)
    {
        if(y&1)
        res=(res*x);
        x=(x*x);
        y/=2;
    }
    return res;
}

long int root(long int x)
{
    while(idx[x]!=x)
    x=idx[x];
    return x;
}

void union1(long int x,long int y)
{
    idx[root(x)]=root(y);
}
long int n,w;
pair<long int,long int> a[101];
long long int dp[100001][101];
long long int fun(long int ww,long int i)
{
    if(i==n)
    return 0;
    if(dp[ww][i]!=-1)
    return dp[ww][i];
    long long int temp2;
    long long int temp1=fun(ww,i+1);
    if(ww-a[i].first>=0)
    {
     temp2=fun(ww-a[i].first,i+1);
    dp[ww][i]=max(temp1,a[i].second+temp2);
    }
    else
    dp[ww][i]=temp1;
    return dp[ww][i];
}
int main() {
	
	cin>>n>>w;
     for(long int i=0;i<n;i++)
     {
         cin>>a[i].first>>a[i].second;
     }
	for(long int i=0;i<100001;i++)
	{
	    for(long int j=0;j<101;j++)
	    dp[i][j]=-1;
	}
	long long int ans=fun(w,0);
	cout<<ans;
	return 0;
}

Measured memory_bytes: 79104
package main

import (
	"bufio"
	"fmt"
	"index/suffixarray"
	"os"
	"strconv"
)

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 1000005), 1000005)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}

func getNextUint64(scanner *bufio.Scanner) uint64 {
	i, _ := strconv.ParseUint(getNextString(scanner), 10, 64)
	return i
}

func getNextFloat64(scanner *bufio.Scanner) float64 {
	i, _ := strconv.ParseFloat(getNextString(scanner), 64)
	return i
}

func main() {
	fp := os.Stdin
	wfp := os.Stdout
	cnt := 0

	if os.Getenv("MASPY") == "ますピ" {
		fp, _ = os.Open(os.Getenv("BEET_THE_HARMONY_OF_PERFECT"))
		cnt = 2
	}
	if os.Getenv("MASPYPY") == "ますピッピ" {
		wfp, _ = os.Create(os.Getenv("NGTKANA_IS_GENIUS10"))
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(wfp)
	solve(scanner, writer)
	for i := 0; i < cnt; i++ {
		fmt.Fprintln(writer, "-----------------------------------")
		solve(scanner, writer)
	}
	writer.Flush()
}

func solve(scanner *bufio.Scanner, writer *bufio.Writer) {
	n := getNextInt(scanner)
	s := getNextString(scanner)
	bb := []byte(s)
	sa := suffixarray.New(bb)

	l := 0
	r := n>>1 + 1
	for l+1 < r {
		m := (l + r) >> 1
		ok := false
		for i := 0; !ok && i+m <= n; i++ {
			index := sa.Lookup(bb[i:i+m], -1)
			if len(index) == 0 {
				continue
			}
			for _, v := range index {
				if v < i+m {
					continue
				}
				ok = true
				break
			}
		}
		if ok {
			l = m
			continue
		}
		r = m
	}

	fmt.Fprintln(writer, l)
}


Measured memory_bytes: 6528
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{
    int k,n,a[100005],b[100005];
    scanf("%d%d",&k,&n);
    for(int i=0;i<k;i++)
        scanf("%d",&a[i]);
    sort(a,a+k);
    int w=0;
    for(int i=0;i<k-n+1;i++)
    {
        b[w++]=a[i+n-1]-a[i];
    }
    int min=b[0];
    for(int j=0;j<w;j++)
    {
        if(b[j]<min)
            min=b[j];
    }
    printf("%d\n",min);
    return 0;
}

Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;

  while(1) {
    int cnt = 0;
    cin >> n;
    if (n == 0) break;
    if (n == 1) cout << 1 << endl;
    else {
      for (int i = n+1; i < 2*n; i++) {
        int flag = 0;
        int jj = 0;
        for (int j = 2; j <= sqrt(i); j++) {
          if (i % j == 0) {flag = 1; break;}
        }
        
        if (flag == 0) {cnt++; /*cout << i << endl;*/}
      }
      cout << cnt << endl;
    }
  }
  return 0;
}



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

int main(){
  string s;
  int k;
  cin >> s >> k;
  int n = s.size();
  for(int i=0; i<n; ++i){
    if(s[i] == 'a') continue;
    if('z'+1 -s[i] <= k){
      k -= 'z'+1 -s[i];
      s[i] = 'a';
    }
  }
  s[n-1] += k%26;
  if(s[n-1] > 'z') s[n-1] -= 26;
  cout << s << endl;
}

Measured memory_bytes: 3748
from collections import deque
#import sys
#input = sys.stdin.readline


d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
d_ = [-2, -1, 0, 1, 2]


h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
s = [input() for i in range(h)]
INF = 10 ** 6

ch, cw = ch - 1, cw - 1
dh, dw = dh - 1, dw - 1
visited = [[INF] * w for i in range(h)]

visited[ch][cw] = 0
val = 0
q = deque([(ch, cw, val)])
while q:
    i, j, val = q.popleft()
    if val > visited[i][j]:
        continue
    val = visited[i][j]

    for di, dj in d:
        nxt_i, nxt_j = i + di, j + dj
        if not(0 <= nxt_i < h and 0 <= nxt_j < w):
            continue
        elif s[nxt_i][nxt_j] == "#":
            continue
        elif visited[nxt_i][nxt_j] > val:
                visited[nxt_i][nxt_j] = val
                q.appendleft((nxt_i, nxt_j, val))

    for di in d_:
        for dj in d_:
            nxt_i, nxt_j = i + di, j + dj
            if not(0 <= nxt_i < h and 0 <= nxt_j < w):
                continue
            elif s[nxt_i][nxt_j] == "#":
                continue
            elif visited[nxt_i][nxt_j] > val + 1:
                visited[nxt_i][nxt_j] = val + 1
                q.append((nxt_i, nxt_j, val + 1))

if visited[dh][dw] == INF:
    print(-1)
else:
    print(visited[dh][dw])

Measured memory_bytes: 97544
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1<<28;

struct point {
    int v;
    int d;
    int m;
};

int main() {
    int N, M, S, T, u, v;
    cin >> N >> M;
    vector<vector<int>> V(N);
    for ( int i = 0; i < M; i++ ) {
        cin >> u >> v;
        u--;
        v--;
        V[u].push_back(v);
    }
    cin >> S >> T;
    S--;
    T--;

    vector<int> dst0(N, INF), dst1(N, INF), dst2(N, INF);
    queue<point> q;
    q.push(point{S, 0, 0});

    while ( !q.empty() ) {
        point p = q.front();
        q.pop();

        if ( p.m == 0 ) {
            if ( dst0[p.v] <= p.d ) continue;
            dst0[p.v] = p.d;
        } else if ( p.m == 1 ) {
            if ( dst1[p.v] <= p.d ) continue;
            dst1[p.v] = p.d;
        } else if ( p.m == 2 ) {
            if ( dst2[p.v] <= p.d ) continue;
            dst2[p.v] = p.d;
        }

        for ( int i = 0; i < V[p.v].size(); i++ ) {
           q.push(point{V[p.v][i], p.d + 1, (p.m + 1) % 3});
        }
    }
    
    ll ans = dst0[T] < INF ? dst0[T] / 3 : -1;
    cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 6912
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	int a,b,sum=0;
	for(int i=1;i<=n;i++)
	{
		cin>>a>>b;
		sum+=(b-a+1);
	}
	cout<<sum;
	return 0;
}

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

using namespace std;


int main(){
    int N, K, d;
    cin >> N >> K;
    vector<int> sunuke(N, 0);
    for(int i=0; i<K; i++){
        cin >> d;
        for(int k=0; k<d; k++){
            int A;
            cin >> A;
            sunuke.at(A-1)++;
        }
        
    }
    int ans = 0;
    for(auto s: sunuke){
        if(s<1){
            ans++;
        }
    }
    cout << ans << endl;
        
    return 0;
}



Measured memory_bytes: 3632
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <vector>
#include <math.h>
#include <queue>
#include <map>
#define ll long long
const int MOD = 1e9+7;
using namespace std;

int main(){
	int n, k, coun = 0, happy = 0;
	string s;
	cin >> n >> k >> s;

	if (s[0] == 'R' && s[1] == 'R') happy++;
	if (s[n-1] == 'L' && s[n-2] == 'L') happy++;
	for (int i = 1; i < n-1; i++){
		if (s[i] == 'L' && s[i-1] == 'L') happy++;
		if (s[i] == 'R' && s[i+1] == 'R') happy++;
	}

	for (int i = 1; i < s.length(); i++){
		if (s[i] != s[i-1]) coun++;
	}
	if (coun/2 + coun%2 <= k) cout << happy + coun << endl;
	else cout << happy + 2*k << endl;
	return 0;
}


Measured memory_bytes: 512
#include<stdio.h>

int main(){
	int num[3];
	int tmp,i,p,q;
	
	for(i = 0; i < 3; i++){
	scanf("%d",&num[i]);
	}
	
	for(p = 0; p < 2; p++){
		for(q = p + 1; q < 3; q++){
			if(num[p] > num[q]){
				tmp = num[p];
				num[p] = num[q];
				num[q] = tmp;
			}
		}
	}
	for(i = 0; i < 3; i++){
	    if (i < 2)
		printf("%d ",num[i]);
		else
	    printf("%d\n",num[i]);
	
	}

	return 0;
}


Measured memory_bytes: 2104
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n,k;
  k=1;
  cin>>n;
  vector<string> vec(n);
  vector<int> answer(n);
  for(int i=0; i<n; i++){
    cin>>vec.at(i);
    answer.at(i)=1;
  }
  sort(vec.begin(), vec.end());
  for(int i=0; i<n-1; i++){
    if(vec.at(i)==vec.at(i+1)){
      answer.at(i+1)=answer.at(i)+answer.at(i+1);
      answer.at(i)=0;
      k=max(k,answer.at(i+1));
    }
  }
  for(int i=0; i<n; i++){
    if(answer.at(i)==k){
      cout<<vec.at(i)<<endl;
    }
  }
}

Measured memory_bytes: 15104
#include<bits/stdc++.h>
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>

using namespace std;
#define EPS 1e-9
#define MAX 505
#define pb push_back
#define mp make_pair
#define ins insert
#define fi first
#define se second
#define pi acos(-1.0)
#define mod 100000007
#define inf 2147483647
#define ll long long int
#define sss stringstream
#define oss ostringstream
#define iss istringstream
#define llu long long unsigned

#define _sq(a) (a)*(a)
#define sz(a) ((int)a.size())
#define gcd(a,b)    __gcd(a,b)
#define lcm(a,b) ((a)*((b)/gcd(a,b)))
#define _max3(a,b,c) max(a, max(b,c))
#define _min3(a,b,c) min(a, min(b,c))
#define FOR(i, n) for(i=0; i<(int)n; i++)
#define FOR1(i, n) for(i=1; i<=(int)n; i++)
#define mem(a) memset(a, 0, sizeof(a))
#define _set(a) memset(a,-1,sizeof(a))
#define FORI(i, a, b) for(i=a; i>=(int)b; i--)
#define FORab(i, a, b) for(i=a; i<=(int)b; i++)
#define popcount(n) __builtin_popcount(n)
#define popcountl(n) __builtin_popcountll(n)
#define sort_rev(a) sort(a.rbegin(), a.rend())
#define sort_all(a) sort(a.begin(), a.end())
#define dis_twopoints(x1,y1,x2,y2) sqrt(_sq(x1-x2) + _sq(y1-y2))
#define foreach(i,n) for(__typeof((n).begin())i =(n).begin();i!=(n).end();i++)

//If Long Long (mask & (1LL << k))
#define check(mask, k) (mask & (1 << k))
#define set1(mask, k) (mask | (1 << k))
#define set0(mask ,k) (mask & (~(1<<k)))

#define SD(a) scanf("%d",&a)
#define SLF(a) scanf("%lf",&a)
#define SC(a) scanf("%c",&a)
#define SS(a) scanf("%s",a)
#define SLLD(a) scanf("%lld", &a)
#define Si64(a) scanf("%I64d", &a)

#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
int main()
{
    double a,b,c,d,e,f,x,y,fl,clx,cly;
    while((cin>>a>>b>>c>>d>>e>>f))
    {
        fl=(e*a-b*d);
        clx=c*e-b*f;
        if(clx==0)
            x=0.0;
        else
            x=clx/fl;
        cly=f*a-c*d;
        if(cly==0)
            y=0.0;
        else
            y=cly/fl;
        printf("%.3lf %.3lf\n",x,y);
    }
    return 0;
}

Measured memory_bytes: 1236
#!/usr/bin/env python3
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def sum_of_arithmetic_progression(s, d, n):
    return n * (2 * s + (n - 1) * d) // 2


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


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


def solve():
    N = int(input())
    A = list(map(int, input().split()))

    c = defaultdict(int)
    for a in A:
        c[a] += 1

    ans = 0
    for k, v in c.items():
        ans += v * (v - 1) // 2

    for k in range(N):
        tmp = ans
        tmp -= c[A[k]] * (c[A[k]] - 1) // 2
        tmp += max(0, (c[A[k]] - 1) * (c[A[k]] - 2) // 2)
        print(tmp)


def main():
    solve()


if __name__ == '__main__':
    main()


Measured memory_bytes: 33208
import sys
from collections import Counter, deque, defaultdict
from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
from functools import reduce
from math import ceil, floor, log10, factorial
import math

sys.setrecursionlimit(1000000)

MOD = 10 ** 9 + 7

INF = float('inf')
# N = int(input())
# A = [int(x) for x in input().split()]
# A = [int(input()) for _ in range(N)]
# dp = [[0] * 100 for _ in range(100)]
# dp = defaultdict(lambda: float('inf'))
# print('hoge', file=sys.stderr)

N, M = [int(x) for x in input().split()]

# E = {set() for _ in range(N + 1)}
E = defaultdict(lambda: set())

for i in range(M):
    u, v = [int(x) for x in input().split()]
    u -= 1
    v -= 1
    E[3 * u].add(3 * v + 1)
    E[3 * u + 1].add(3 * v + 2)
    E[3 * u + 2].add(3 * v)

S, T = [int(x) for x in input().split()]
S = 3 * (S - 1)
T = 3 * (T - 1)


def bfs(e, start, end):
    open = deque([start])
    w = dict()
    w[start] = 0
    while len(open) != 0:
        target = open.popleft()
        for next in E[target]:
            if not next in w:
                open.append(next)
                w[next] = w[target] + 1

    return w[end] // 3 if end in w else -1


print(bfs(E, S, T))


Measured memory_bytes: 131652
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ

		Scanner sc1 = new Scanner(System.in);
		String s = sc1.next();
		String t = sc1.next();
		boolean flag = false;

		for (int i = 0 ; i < s.length() ; i++ ) {
			String str;
			str = s.substring(1,s.length()) + s.substring(0, 1);
			//System.out.println(str);
			//System.out.println(s);
			if ( str.equals(t)) {
				flag = true;
				break;
			}
			s = str;
		}

		if(flag) {
			System.out.println("Yes");
		}
		else {
			System.out.println("No");
		}

		sc1.close();
	}

}

Measured memory_bytes: 23124
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        A solver = new A();
        solver.solve(1, in, out);
        out.close();
    }

    static class A {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            // 入力
            String S = in.next();
            boolean ok = false;
            if ('a' <= S.charAt(0) && S.charAt(0) <= 'z') ok = true;
            out.println(ok ? "a" : "A");

        }

    }
}



Measured memory_bytes: 35828
#include <math.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>

#define ll long long
#define MAX_N 1000005
#define MOD 10007

using namespace std;

double calc(ll bx, ll by, ll ax, ll ay) {
  return sqrt(((ax - bx) * (ax - bx)) + ((ay - by) * (ay - by)));
}

int main() {
  ll N;
  cin >> N;
  vector<ll> x(N), y(N);
  for (int i = 0; i < N; i++) {
    cin >> x[i] >> y[i];
  }

  vector<ll> town;
  for (int i = 1; i <= N; i++) {
    town.push_back(i);
  }

  sort(town.begin(), town.end());

  double sum = 0;
  ll count = 0;
  do {
    count++;
    for (int i = 0; i < N - 1; i++) {
      sum += calc(x[town[i] - 1], y[town[i] - 1], x[town[i + 1] - 1],
                  y[town[i + 1] - 1]);
    }
  } while (next_permutation(town.begin(), town.end()));

  double ave = (double)sum / count;
  printf("%.10f", ave);
}

Measured memory_bytes: 256
from collections import deque
h,w = map(int,input().split())
s = [ list(input()) for i in range(h)]

def bfs(startx,starty):
    d = [[-1]*w for i in range(h)]
    q = deque([[startx,starty]])
    d[startx][starty] = 0
    cnt = 0
    while(q):
        x,y = q.popleft()
        for i,j in ([1,0],[-1,0],[0,1],[0,-1]):
            new_x,new_y = x+i,y+j
            if (new_x>h-1) or (new_x<0) or (new_y>w-1) or (new_y<0):
                continue
        
            elif s[new_x][new_y] == '#':
                continue
        
            elif d[new_x][new_y] == -1:
                d[new_x][new_y] = d[x][y]+1
                q.append([new_x,new_y])
                cnt = max(cnt,d[new_x][new_y])
    
    return cnt

ans = 0

for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            ans = max(ans,bfs(i,j))

print(ans)

Measured memory_bytes: 3316
N, D = map(int, input().split()) # 横に2個
X = []
c = 0
for _ in range(N):
    Xi = list(map(int, input().split())) # １行に別れてるとき
    for x in X:
        dis = 0
        for i in range(D):
            dis += (x[i] - Xi[i])**2
        for k in range(200):
            if dis == k**2:
                c += 1
    X.append(Xi)

print(c)

Measured memory_bytes: 3060
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define Max 100001
#define inf 1000000000000000
using namespace std;
int n,m,flag;
int first[Max * 2],nextv[Max * 2],u[Max * 2],v[Max * 2],s[Max * 2];
long long vis[2][Max],l = 0,r = inf,ans;
void dfs(int from,int tag,long long va) {
    if(flag)return;
    int k = first[from];
    while(k != -1) {
        if(flag)return;
        int vtag = (tag == 1);
        int to = v[k];
        long long lva = s[k] - va;
        if(vis[vtag][to] != inf) {
            if(vis[vtag][to] == lva) {
                k = nextv[k];
                continue;
            }
            else {
                flag = 1;
                return;
            }
        }
        vis[vtag][to] = lva;
        if(vtag)r = min(r,lva);
        else l = max(l,-lva);
        if(r - l <= 1){///范围冲突 没有解
            flag = 1;
            return;
        }
        dfs(to,-tag,lva);
        k = nextv[k];
    }
}
int main() {
    scanf("%d%d",&n,&m);
    memset(first,-1,sizeof(first));
    for(int i = 1;i <= n;i ++) {
        vis[0][i] = vis[1][i] = inf;
    }
    for(int i = 0;i < m;i ++) {
        scanf("%d%d%d",&u[i],&v[i],&s[i]);
        u[i + m] = v[i];
        v[i + m] = u[i];
        s[i + m] = s[i];
        nextv[i] = first[u[i]];
        first[u[i]] = i;
        nextv[i + m] = first[u[i + m]];
        first[u[i + m]] = i + m;
    }
    dfs(1,1,0);///dfs遍历所有点和第一个点的关系，如果有冲突flag为1 冲突就是说得到于同一点的同一关系的值不同比如a1 + a2 = 3 和 a1 + a2 = 4
    if(!flag) {///遍历后无冲突
        long long temp = -1;
        for(int i = 1;i <= n;i ++) {
            if(vis[0][i] != inf && vis[1][i] != inf) { ///可以确定a1
                long long d = vis[1][i] - vis[0][i];
                if(d % 2) {
                    flag = 1;
                    break;
                }
                temp = d / 2;
            }
        }
        if(!flag) {
            if(temp != -1) {///确定a1 解唯一
                ans = 1;
            }
            else ans = r - l - 1;
        }
    }
    printf("%lld",ans);
    return 0;
}


Measured memory_bytes: 15872
# -*- coding: utf-8 -*-
import numpy as np
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect

sys.setrecursionlimit(10**6)
def zz():
    return list(map(int, sys.stdin.readline().split()))


def z():
    return int(sys.stdin.readline())


def S():
    return sys.stdin.readline()


def C(line):
    return [sys.stdin.readline() for _ in range(line)]

N = z()
A = [0]*N
X = {}
Y = {}
for i in range(N):
    A[i] = z()
    X[i] = [0]*A[i]
    Y[i] = [0]*A[i]
    for j in range(A[i]):
        x, y = zz()
        X[i][j] = x-1
        Y[i][j] = y
ans = 0
for bits in itertools.product([0, 1], repeat=N):
    # print("================")
    # print(bits)
    false_flg = False
    for i, b in enumerate(bits):
        if (b == 1):
            # print('i=', i)
            for x, y in zip(X[i], Y[i]):
                # print(x, y)
                if (bits[x] != y):
                    # print(False)
                    false_flg = True
                if false_flg:
                    break
            if false_flg:
                break
    if false_flg:
        continue
    else:
        ans = max(ans, sum(bits))
print(ans)

Measured memory_bytes: 27220
#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>

using namespace std;

#define MP make_pair
#define PB push_back

typedef pair<pair<string, int>, int> Rest; // city, point, id

int main(void){
  int n, p;
  string s;
  vector<Rest> restaurants;
  
  cin >> n;
  for (int i=1; i<=n; i++){
    cin >> s >> p;
    restaurants.PB(MP(MP(s,-p),i));
  }
  sort(restaurants.begin(), restaurants.end());
  for (int i=0; i<n; i++){
    cout << restaurants[i].second << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <functional>
using namespace std;
using namespace __gnu_pbds;

#define ll long long
#define mk make_pair

template <class key, class cmp = std::less<key>>
using ordered_set = tree<key, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
const ll mod = 1e9 + 7;

/*
    if you have any question about any part of my code,
    please don't shy to ask anytime :)
*/



void solve()
{
    ll n,k;
    cin>>n;
    vector<ll>x(n);
    ll sum=0;
    unordered_map<ll,ll>h;
    for(int i=0;i<n;i++)
    {
        cin>>x[i];
        h[x[i]]++;
        sum+=x[i];
    }

    cin>>k;
    while(k--)
    {
        ll a,b;
        cin>>a>>b;
        sum-=(a*h[a]);
        sum+=(b*h[a]);
        h[b]+=h[a];
        h[a]=0;
        cout<<sum<<endl;
    }
}

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

    // ll t;
    // cin >> t;

    // while (t--)
    // {
    //     solve();
    // }
    solve();
    return 0;
}

Measured memory_bytes: 7932
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string S;
  string T;
  cin >> S >> T;
  int A;
  int B;
  cin >> A >> B;
  string U;
  cin >> U;
  if ( S == U ) {
    cout << A - 1 << " " << B << endl;
  }
  if ( T == U ) {
    cout << A << " " << B - 1 << endl;
  }
}


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

int main() {
string s;
cin >> s;
char a = s[5];
char b = s[6];
int x = a - '0';
int y = b - '0';
if (x  == 1 or y > 4){
  cout << "TBD" << endl;
}
else{
  cout << "Heisei" << endl;
}
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <utility>
#include <tuple>
#include <cctype>
#include <bitset>
#include <complex>
#include <cmath>
using namespace std;
//#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3fLL
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pint;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
int dx[8]={0,0,-1,1,1,1,-1,-1};
int dy[8]={-1,1,0,0,1,-1,1,-1};
const int SIZE=100;
//ここまでテンプレ
int main(){
	int A[3]={};
	for(int i=0;i<3;i++)
		cin>>A[i];
	sort(A,A+3,greater<int>());
	int count=0;
	while(1){
		if(A[0]==A[1] && A[1]==A[2])
			break;
		if(A[0]>A[1]){
			A[1]++;
			A[2]++;
			count++;
		}
		else if(A[0]==A[1] && A[1]>A[2]){
			A[2]+=2;
			count++;
		}
		sort(A,A+3,greater<int>());
		//cout<<A[0]<<" "<<A[1]<<" "<<A[2]<<endl;
	}
	cout<<count<<endl;
	return 0;
}

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

void solve(){
	int x,y;
	scanf("%d%d",&x,&y);
	int ret;
	if(x==0){
		if(y>=0){
			ret = y;
		} else {
			ret = abs(y)+1;
		}
	} else {
		if(x<y){
			ret = y-x;
			ret = min(ret, 2 + abs(y-x));
			if(x<0){
				ret = min(ret, 1 + abs(y+x));
			}
		} else {
			int u = -x;
			ret = 1 + abs(y-u);
			ret =min(ret, 2 + abs(abs(y)-abs(x)));
		}
	}
	cout<<ret<<endl;
}
int main(){
	//freopen("input.txt","r",stdin);
	solve();
}

Measured memory_bytes: 256
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <random>
#include <iterator>

using namespace std;

#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(v) reverse((v).begin(),(v).end())
#define ANS(ans) cout<<(ans)<<endl;
#define UNIQUE(v) (v).erase(unique((v).begin(), (v).end()), (v).end());
typedef vector<int> VI;
typedef pair<int, int> P;

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n)  for (int i = 0; i < (n); ++i)


int main() {
	string s;
	cin >> s;

	int n = s.length();
	int ans1 = 0;
	int ans2 = 0;

	REP(i, n) {
		if (i % 2 == 0) {
			if (s[i] == '0') {

			}
			else {
				ans1++;
			}
		}
		else {
			if (s[i] == '1') {

			}
			else {
				ans1++;
			}
		}
	}

	REP(i, n) {
		if (i % 2 == 0) {
			if (s[i] == '1') {

			}
			else {
				ans2++;
			}
		}
		else {
			if (s[i] == '0') {

			}
			else {
				ans2++;
			}
		}
	}

	ANS(min(ans1, ans2));

	return 0;
}


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

using namespace std;

#define ll long long
#define pb push_back

const int mod = 1e9 + 7;
const int INF = 1e9;
const int N = 2e5 + 5;

int main(){
	string s, t;
	cin >> s >> t;
	int cnt = 0;
	for(int i = 0; i < s.size(); i++){
		if(s[i] != t[i]) cnt++;
	}
	cout << cnt << endl;
}

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

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define FOR(i, n) for (int i = 0; i < int(n); i++)
#define FOR1(i, m, n) for (int i = int(m); i < int(n); i++)
#define MAX(a, b) ((a) >= (b) ? (a) : (b))
#define MIN(a, b) ((a) <= (b) ? (a) : (b))

int main(int argc, char *argv[]) {
  int N, M, Q;
  vector<vector<int>> S;
  vector<vector<int>> ECOL, EROW, V;

  cin >> N >> M >> Q;

  S.resize(N);
  ECOL.resize(N + 1);
  EROW.resize(N + 1);
  V.resize(N + 1);
  FOR(i, N) S[i].resize(M, 0);
  FOR(i, N + 1) {
    ECOL[i].resize(M + 1, 0);
    EROW[i].resize(M + 1, 0);
    V[i].resize(M + 1, 0);
  }

  FOR(i, N) {
    FOR(j, M) {
      char c;
      scanf(" %c", &c);
      S[i][j] = c - '0';
    }
  }

  FOR(i, M) { V[1][i + 1] = S[0][i]; }
  FOR1(i, 2, N + 1) {
    FOR1(j, 1, M + 1) { V[i][j] = V[i - 1][j] + S[i - 1][j - 1]; }
  }
  FOR(i, N + 1) {
    FOR1(j, 1, M + 1) { V[i][j] += V[i][j - 1]; }
  }

  FOR1(i, 2, N + 1) {
    FOR1(j, 1, M + 1) {
      ECOL[i][j] = ECOL[i - 1][j] + S[i - 2][j - 1] * S[i - 1][j - 1];
    }
  }
  FOR(i, N + 1) {
    FOR1(j, 1, M + 1) { ECOL[i][j] += ECOL[i][j - 1]; }
  }

  FOR1(i, 1, N + 1) {
    FOR1(j, 2, M + 1) {
      EROW[i][j] = EROW[i][j - 1] + S[i - 1][j - 2] * S[i - 1][j - 1];
    }
  }
  FOR1(i, 1, N + 1) {
    FOR(j, M + 1) { EROW[i][j] += EROW[i - 1][j]; }
  }

  FOR(i, Q) {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;

    int v = V[x2][y2] - V[x2][y1 - 1] - V[x1 - 1][y2] + V[x1 - 1][y1 - 1];
    int e = ECOL[x2][y2] - ECOL[x2][y1 - 1] - ECOL[x1][y2] + ECOL[x1][y1 - 1] +
            EROW[x2][y2] - EROW[x2][y1] - EROW[x1 - 1][y2] + EROW[x1 - 1][y1];

    cout << v - e << endl;
  }

  return 0;
}


Measured memory_bytes: 64640
#include <iostream> 
using namespace std; 
int main(){ 
  string s; 
  cin>>s; 
  if(s=="RRR"){ 
    cout<<3<<endl; 
    } 
  else if(s=="RRS"||s=="SRR"){ 
    cout<<2<<endl; 
    } 
  else if(s=="SSS"){ 
    cout<<0<<endl; 
    } 
  else{ 
    cout<<1<<endl; 
    } 
  return 0; 
  }


Measured memory_bytes: 3224