akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <unistd.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<ll,ll> P;
 
long long int INF = 3e18;
const ll fact_table = 800008;
double Pi = 3.1415926535897932384626;
 
//vector<ll> G[550010];
vector<P> tree[500010];
priority_queue <ll> pql;
priority_queue <P> pqp;
//big priority queue
priority_queue <ll,vector<ll>,greater<ll> > pqls;
priority_queue <P,vector<P>,greater<P> > pqps;
//small priority queue
//top pop
 
ll dx[8]={1,0,-1,0,1,1,-1,-1};
ll dy[8]={0,1,0,-1,1,-1,-1,1};
char dir[] = "DRUL";
//ll bit[500005];
//↓,→,↑,←
 
 
#define p(x) cout<<x<<"\n";
#define el cout<<endl;
#define pe(x) cout<<(x)<<" ";
#define ps(x) cout<<fixed<<setprecision(25)<<x<<endl;
#define pu(x) cout<<(x);
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define CLEAR(a) a = decltype(a)(); 
 
 
//ll mod = 998244353;
ll mod = 1000000007;
 
ll rui(ll number1,ll number2){
 
    if(number2 == 0){
        return 1;
    }else{
        ll number3 = rui(number1,number2 / 2);
        number3 *= number3;
        number3 %= mod;
        if(number2%2==1){
            number3 *= number1;
            number3 %= mod;
        }
        return number3;
    }
}
ll gcd(ll number1,ll number2){
 
    if(number1 > number2){
        swap(number1,number2);
    }
    if(number1 == 0 || number1 == number2){
        return number2;
    }else{
        return gcd(number2 % number1,number1);
    }
}
void YES(bool condition){
 
    if(condition){
        p("YES");
    }else{
        p("NO");
    }
    return;
}
void Yes(bool condition){
 
    if(condition){
        p("Yes");
    }else{
        p("No");
    }
    return;
}
 
/*
ll fact[fact_table + 5],rfact[fact_table + 5];
 
void c3_init(){
    fact[0] = rfact[0] = 1;
    for(ll i=1; i<=fact_table; i++){
        fact[i] = (fact[i-1]*i) % mod;
    }
    rfact[fact_table] = rui(fact[fact_table],mod - 2);
    for(ll i=fact_table; i>=1; i--){
       rfact[i-1] = rfact[i] * i;
       rfact[i-1] %= mod;
    }
    return;}
ll c3(ll n,ll r){
    return (((fact[n] * rfact[r]) % mod ) * rfact[n-r]) % mod;}
*/
 
ll n,m,num,sum,a,b,c,d,e,g,h,w,i,j,q,r,l;
ll k;
ll ans;
ll x[200005], y[500005], z[200005];
bool used[500005];
char s[500005];
ll query;

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

    cin >> n >> s;
    for(ll i=0;i<n - 2;i++){
        if(s[i] == 'A' && s[i + 1] == 'B' && s[i + 2] == 'C')ans ++;
    }
    p(ans);


    return 0;
}











Measured memory_bytes: 13824
import random


d = int(input())
c = list(map(int,input().split()))
s = []

class field:
    def __init__(self):
        self.ans = [-1 for i in range(365)]
        self.last = [-1 for i in range(26)]


    def score_day(self,day,type):
        inc = s[day][type]
        dec = 0
        for i in range(26):
            dec += c[i]*(day-self.last[i])

        return  inc-dec


for i in range(d):
    arr = list(map(int,input().split()))
    s.append(arr)

best_score = 0
alloc = []

F = field()
ans = 0
good = []
childs = 30
for day in range(d):
    if day == 0:
        tp_scores = []
        for j in range(25):
            prob = j
            befl = F.last[prob]
            F.last[prob] = day
            sc = F.score_day(day, prob)
            tp_scores.append([-sc, j,F.last.copy(),str(j)])

            F.last[prob] = befl

        tp_scores.sort()
        good = tp_scores
    else:
        tp_scores = []
        for i in range(min(childs,len(good))):
            befs = good[i][0]
            befp = good[i][1]
            befl = good[i][2]
            befa = good[i][3]
            F.last = befl
            for j in range(25):
                prob = j
                bt = F.last[prob]
                F.last[prob] = day
                sc = F.score_day(day,prob)
                tp_scores.append([befs-sc,j,F.last.copy(),befa+","+str(j)])

                F.last[prob] = bt

        tp_scores.sort()
        good = tp_scores[:childs]

# print(good[0])


# for g in good:
#     tp = 0
#     root = list(map(int,g[-1].split(",")))
#     F = field()
#     for i in range(len(root)):
#         F.ans[i] = root[i]
#         F.last[root[i]] = i
#         tp += F.score_day(i,root[i])
#     print(root,tp)

# print("bestscore:"+str(best_score))

root = map(int,good[0][-1].split(","))

for r in root:
    print(r+1)


Measured memory_bytes: 126572
#include <algorithm>
#include <iostream>
#include <string>
#include <random>
#include <cassert>
#include <cstring>
#include <chrono>
#include <map>

using namespace std;

typedef long long ll;

int main()
{
  int n;
  cin >> n;
  map<ll, ll> m;
  m[0] = 1;
  ll sum = 0;
  ll result = 0;
  for (int i = 0; i < n; ++i) {
    ll x;
    cin >> x;
    sum += x;
    if (m.count(sum)) {
      result += m[sum];
    }
    m[sum]++;
  }
  cout << result << endl;
  return 0;
}


Measured memory_bytes: 12800
#include<iostream>

using namespace std;

int main()
{
	char S[5];
	int flag=0;

	cin>>S;

	for(int i=0; i<4; i++)
	{
		if(S[i]==S[i+1])
		{
			flag=1;
			break;
		}
	}

	if(flag==0)
		cout<<"Good";
	else
		cout<<"Bad";
	return 0;
}


Measured memory_bytes: 256
if __name__ == '__main__':
    n, m = map(int, input().split())
    l = sorted(tuple(int(s) for s in input().split()) for _ in range(n))
    ans = 0
    for a, b in l:
        if m == 0:
            break
        ans += min(m, b) * a
        m = max(m - b, 0)
    print(ans)


Measured memory_bytes: 16996
#include <bits/stdc++.h>	//Knapsack 2
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int maxn = 110;
const int maxm = 100100;
const int inf = 1e9;

typedef long long int ll;
typedef pair<int,int> ii;

int dp[maxm];
int wei[maxn],val[maxn];
int n,m,total;

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin>>n>>m;
	
	for(int i=1;i<=n;++i)
	{		
		cin>>wei[i]>>val[i];
		total += val[i];
	}

	for(int i=1;i<=total;++i)
		dp[i] = inf;
	
	dp[0] = 0;

	
	for(int i=1;i<=n;++i)
	{
		int w = wei[i],v = val[i];

		for(int j=total;j>=v;j--)
		{
			dp[j] = min(dp[j],dp[j - v] + w);
		}
	}

 	for(int i=total;total>=0;--i)
 	{
 		if(dp[i] <= m)
 		{
 			cout<<i<<"\n";
 			return 0;
 		}
 	}

}

Measured memory_bytes: 4004
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main {
    public static void main(String[] args) {
        String line = readLine(System.in);
        StringTokenizer token = new StringTokenizer(line, " ");
        int v = Integer.parseInt(token.nextToken());
        int h = Integer.parseInt(token.nextToken());
        System.out.println((v * h) + " " + (v * 2 + h * 2));
    }

    private static String readLine(InputStream in) {
        String line = null;
        BufferedReader reader = null;

        try {
            reader = new BufferedReader(new InputStreamReader(in));
            line = reader.readLine();
        } catch (IOException e) {
            throw new RuntimeException(e);
        } finally {
            if (reader != null) {
                try {
                    reader.close();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
        }

        return line;
    }
}

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

int main(){
long n,t,a,b,c,m,x,mi,aux;
cin>>n>>m>>x;
deque<long> A[n];
long R[n];
long au[m];
for(int i=0;i<n;i++){
        cin>>R[i];
for(int l=0;l<m;l++){
    cin>>a;
    A[i].push_back(a);
}
}mi=10000000;
for(int i=0;i<(1<<n);i++){
    memset(au,0,sizeof(au));
    c=0;aux=0;
    for(int j=0;j<n;j++){
        if(i&(1<<j)){
            aux=aux+R[j];
            for(int l=0;l<m;l++){
                if(au[l]!=-1)au[l]=au[l]+A[j][l];
                if(au[l]>=x){au[l]=-1;c++;}
            }
        }
    }
    if(c==m)mi=min(mi,aux);
}
if(mi==10000000)cout<<"-1"<<endl;
else cout<<mi<<endl;
return 0;
}


Measured memory_bytes: 3636
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
A.sort()
cnt = Counter(A)
divs = set()
for i in range(N):
  if A[i] in divs:
    continue
  if cnt[A[i]]>=2:
    divs.add(A[i])
  for j in range(2, 10**6//A[i]+1):
    divs.add(A[i]*j)
ans = 0
for i in range(N):
  if A[i] in divs:
    continue
  ans += 1
print(ans)

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

int main() {
  int N;
  cin >> N;
  vector<int> a(N),b(N),c(N);
  for (int i=0;i<N;i++){
    cin >> a[i] >> b[i] >> c[i];
  }
  int dp[N][3];
  dp[0][0]=a[0];
  dp[0][1]=b[0];
  dp[0][2]=c[0];
  for (int i=1;i<N;i++){
    dp[i][0]=max(dp[i-1][1],dp[i-1][2])+a[i];
    dp[i][1]=max(dp[i-1][2],dp[i-1][0])+b[i];
    dp[i][2]=max(dp[i-1][0],dp[i-1][1])+c[i];
  }
  int ans=max(max(dp[N-1][0],dp[N-1][1]),dp[N-1][2]);
  cout << ans << endl;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
const ll MOD = 1e9 + 7;
const int INF = 1e9;
vector<map<int,int>> ch(31);
int link(int channel, int num) {
  if (ch[channel][num] != 0) {
    int last = link(channel, ch[channel][num]);
    ch[channel][num] = 0;
    return last;
  } else {
    return num;
  }
}
int main() {
  int imos[100010] = {};
  int n, C;
  cin >> n >> C;
  for (int i = 0; i < n; i++) {
    int s, t, c;
    cin >> s >> t >> c;
    ch[c][s] = t;
  }
  for (int i = 1; i <= C; i++) {
    for (auto &p: ch[i]) {
      p.second = link(i, p.second);
    }
  }
  for (int i = 1; i <= C; i++) {
    for (auto p: ch[i]) {
      if (p.second == 0) continue;
      imos[p.first - 1]++;
      imos[p.second] --;
    }
  }
  int ans = 1;
  for (int i = 1; i <= 100000; i++) {
    imos[i] += imos[i - 1];
    ans = max(ans, imos[i]);
  }
  cout << ans << endl;
  return 0;
}

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

using P = pair<int,int>;

int main(){
    int n, m;
    while(cin >> m, m){
        vector<P> a(m);
        set<P> st;
        for(int i=0;i<m;i++){
            int x, y;
            cin >> x >> y;
            a[i] = P(x,y);
        }
        cin >> n;
        for(int i=0;i<n;i++){
            int x, y;
            cin >> x >> y;
            st.insert(P(x,y));
        }
        for(int i=1;i<m;i++){
            a[i].first -= a[0].first;
            a[i].second -= a[0].second;
        }
        for(auto p : st){
            int x0 = p.first, y0 = p.second;
            bool ok = true;
            for(int i=1;i<m;i++){
                ok &= st.count(P(a[i].first+x0,a[i].second+y0)) > 0;
            }
            if(ok){
                int dx, dy;
                dx = x0-a[0].first; dy = y0-a[0].second;
                cout << dx << " " << dy << endl;
                break;
            }
        }
    }
    return 0;
}



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

typedef long long int ll;
typedef pair<ll, ll> p_ll;
typedef vector<pair<ll, ll>> vec_p; //vector<pair<ll, ll>> pairs(n) ,pairs.at(i) = make_pair(i*i, i)

#define ture ture
#define flase false
#define falg flag

#define REP(i, x) for (ll i = 0; i < (ll)(x); i++)
#define REPS(i, x) for (ll i = 1; i <= (ll)(x); i++)
#define RREP(i, x) for (ll i = ((ll)(x)-1); i >= 0; i--)
#define RREPS(i, x) for (ll i = ((ll)(x)); i > 0; i--)
#define all(x) (x).begin(), (x).end()

const ll MOD = pow(10, 9) + 7;
const ll LLINF = pow(2, 61) - 1;//llの最大9*10^18
const int INF = pow(2, 30) - 1;

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

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

    ll N;
    string S;
    cin >> N;

    ll D = N % 10;
    N = (N - D) / 10;
    ll C = N % 10;
    N = (N - C) / 10;
    ll B = N % 10;
    N = (N - B) / 10;
    ll A = N % 10;

    ll tmp = 0;

    bool flag = flase;

    REP(i,2){
        REP(j,2){
            REP(k,2){
                if(i==0){
                    tmp = A + B;
                }
                else{
                    tmp = A - B;
                }
                if (j == 0)
                {
                    tmp += C;
                }
                else
                {
                    tmp -= C;
                }
                if (k == 0)
                {
                    tmp += D;
                }
                else
                {
                    tmp -= D;
                }
                if(tmp==7){
                    cout << A;
                    if (i == 0)
                    {
                        cout << "+";
                    }
                    else
                    {
                        cout << "-";
                    }
                    cout << B;
                    if (j == 0)
                    {
                        cout << "+";
                    }
                    else
                    {
                        cout << "-";
                    }
                    cout << C;
                    if (k == 0)
                    {
                        cout << "+";
                    }
                    else
                    {
                        cout << "-";
                    }
                    cout << D;
                    cout << "=7" << endl;
                    flag = true;
                    break;
                }
            }
            if(flag){
                break;
            }
        }
        if (flag)
        {
            break;
        }
    }

}


Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
//#include <boost/multiprecision/cpp_int.hpp>
//using multiInt = boost::multiprecision::cpp_int;

using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename Q_type>
using smaller_queue = priority_queue<Q_type, vector<Q_type>, greater<Q_type>>;

const int MOD_TYPE = 1;
const ll MOD = (MOD_TYPE == 1 ? (ll)(1e9 + 7) : 998244353);
const int INF = (int)1e9;
const ll LINF = (ll)4e18;
const double PI = acos(-1.0);

#define REP(i, m, n) for (ll i = m; i < (ll)(n); ++i)
#define rep(i, n) REP(i, 0, n)
#define MP make_pair
#define MT make_tuple
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << endl
#define possible(n) cout << ((n) ? "possible" : "impossible") << endl
#define Yay(n) cout << ((n) ? "Yay!" : ":(") << endl
#define all(v) v.begin(), v.end()
#define NP(v) next_permutation(all(v))
#define dbg(x) cerr << #x << ":" << x << endl;

vector<int> Dx = {0, 0, -1, 1, -1, 1, -1, 1, 0};
vector<int> Dy = {1, -1, 0, 0, -1, -1, 1, 1, 0};

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << setprecision(50) << setiosflags(ios::fixed);
  int n;
  cin >> n;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];
  int q;
  cin >> q;
  rep(qi, q)
  {
    int b, e;
    ll k;
    cin >> b >> e >> k;
    cout << count(a.begin() + b, a.begin() + e, k) << endl;
  }
  return 0;
}



Measured memory_bytes: 3152
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <cmath>
#include <set>
#include <algorithm>
#include <iomanip>

typedef long long ll;
const ll MOD = 1e9 + 7;
const long long INF = 1LL<<60;
const double PI=3.14159265358979323846;
const int NMAX=100005;
using namespace std;


int main(){
    int n,k;
    cin >> n >> k;
    vector<int> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    sort(a.begin(), a.end());

    int ans = 0;
    for(int i = 0; i < k; i++){
        ans += a[i];
    }
    
    cout << ans << endl;

    
    return 0;
}

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

int main() {
  char a;
  cin >> a;
  bool capital = false;
  for(int i = 65; i < 91; i++) {
    if(a== (char)i) {
      capital = true;
      break;
    }
  }
  if(capital)
    cout << 'A' << endl;
  else
    cout << 'a' << endl;
}

Measured memory_bytes: 3588
#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <deque>
#include <algorithm>
#include <queue>
#include <cmath>
#include <map>
#include <complex>
#include <cstring>
#include <cassert>
#include <bitset>

using namespace std;
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define repd(i, a, b) for(int i = (a); i > (b); i--)
#define forIt(it, a) for(__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define forRev(it, a) for(__typeof((a).rbegin()) it = (a).rbegin(); it != (a).rend(); it++)
#define ft(a) __typeof((a).begin())
#define ll long long
#define ld long double
#define fi first
#define se second
#define mk make_pair
#define pb push_back
#define sz(a) (int)(a).size()
#define all(a) (a).begin(), (a).end()
#define bitcount(n) __builtin_popcountll(n)


typedef complex<ld> cplex;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;

const int N = 500000 + 7;
const int M = 20;
const int inf = 1e9 + 7;
const long long linf = 1ll * inf * N * 1000;
const double pi = acos(-1);
const double eps = 1e-7;
const bool multipleTest = 0;


int x[N];
int n;
ll f[N];

void solve() {
    
    f[0] = 1;
    for(int i = 1; i < N; ++i) f[i] = f[i - 1] * i % inf;
    
    cin >> n;
    
    ll ans = 1;
    int pre = -1;
    
    int tol = 0;
    
    for(int i = 1; i <= n; ++i) {
        scanf("%d", x + i);
        if (x[i] == pre + 1) {
            
            ans = (ans * (i - tol)) % inf;
        
            ++tol;
            
        } else {
            x[i] = pre + 2;
            pre = x[i];
        }
    }
    
    ans = ans * f[n - tol] % inf;
    
    cout << ans << '\n';
    
}


int main() {
#ifdef _LOCAL_
    freopen("in.txt", "r", stdin);
    //t1=clock();
#endif
    
    int Test = 1;
    if (multipleTest) {
        cin >> Test;
    }
    for(int i = 0; i < Test; ++i) {
        solve();
    }
    
#ifdef _LOCAL_
    cout<<"\n" << clock() / CLOCKS_PER_SEC<<endl;
#endif
}


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

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

  for (int i = 0; i <= 100 / 4; i++) {
    for (int j = 0; j <= 100 / 7; j++) {
      if (4 * i + 7 * j == N) {
        cout << "Yes" << endl;
        return 0;
      }
    }
  }

  cout << "No" << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    if (n == 1) {
      System.out.println("Hello World");
    } else {
      int a = sc.nextInt();
      int b = sc.nextInt();
      System.out.println(a + b);
    }
  }

}


Measured memory_bytes: 21332
#include<bits/stdc++.h>
using namespace std;
int a[222222];
int main()
{
	int n,t=0;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
		t=t xor a[i];
	}
	for(int i=0;i<n;i++)
	{
		cout<<(a[i] xor t)<<" ";
	}
	return 0; 
 } 

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

main(){
  
  ll n;
  cin>>n;
  vector<ll> a(n);
  for(auto& ai:a)cin>>ai;
  
  map<ll,ll> ecnt,ocnt;
  rep(i,n){
    if(i&1)ocnt[a[i]]++;
    else ecnt[a[i]]++;
  }
  vector<pair<ll,ll>> x,y;
  for(const auto& elm:ecnt)x.emplace_back(elm);
  for(const auto& elm:ocnt)y.emplace_back(elm);
  auto cmp = [&](auto a,auto b){return a.second > b.second;};
  sort(x.begin(),x.end(),cmp);
  sort(y.begin(),y.end(),cmp);
  x.emplace_back(0,0);
  y.emplace_back(0,0);
  if(x[0].first==y[0].first){
    ll s=x[0].second+y[1].second;
    ll t=y[0].second+x[1].second;
    cout<<(n-max(s,t))<<endl;
  }
  else{
    cout<<(n-x[0].second-y[0].second)<<endl;
  }


}


Measured memory_bytes: 9592
import numpy as np
N,W = map(int,input().split())
dp = np.full(N*1000+1,W+1)
dp[0] = 0
for _ in range(N):
    w,v = map(int,input().split())
    dp[v:]=np.minimum(dp[v:],dp[:-v]+w)
print(np.where(dp<=W)[0][-1])


Measured memory_bytes: 14908
A, B, K = map(int, input().split())
l = []
for i in range(K):
  if A + i <= B:
    l.append(A + i)
  if B - i >= A:
    l.append(B - i)
l = list(set(l))
l.sort()
for i in range(len(l)):
  print(l[i])


Measured memory_bytes: 3060
n,m = list(map(int,input().split()))
k = [0]*m
counter = 0
for i in range(0,m):
    k[i] = list(map(int,input().split()))
p = list(map(int,input().split()))

for h in range(0,2**n):
    c = [0]*n
    for s in range(0,n):
        if (h >> s)% 2 == 1:
            c[s] = 1
    for i in range(0,m):
        check = 0
        for j in range(1,k[i][0]+1):
            if c[k[i][j]-1] == 1:
                check += 1
        if check%2 != p[i]:
            break
    else:
        counter += 1

print(counter)

Measured memory_bytes: 3064
import sys
from collections import deque
# https://atcoder.jp/contests/abc142/submissions/7764934
# ほぼまんま。


def main():
    N, M = map(int, input().split())
    E = [set() for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        E[a-1].add(b-1)

    # スタート地点は全て試す
    for start in range(N):
        visited = [0]*N
        Q = deque([(start, {start})])
        append, popleft = Q.append, Q.popleft
        visited[start] = 1

        while Q:
            v, route = popleft()
            # これまで通ってきた頂点と行き先の積集合
            s = route & E[v]
            # sが空集合(ループでない)か、行き先に始点のみが含まれる場合は継続
            # 行き先に始点以外の場所が含まれるなら、もっと良い始点の選び方がある。
            # if not (not s or (s == {start})):
            if s and s != {start}:
                continue
            for dest in E[v]:
                if dest == start:
                    print(len(route))
                    print(*[n+1 for n in route], sep="\n")
                    return
                if visited[dest]:
                    continue
                visited[dest] = 1
                append((dest, route | {dest}))
    print(-1)
    return


if __name__ == '__main__':
    main()


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

int N;
string S[10100];
int cnt[3];
int ans;

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

    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < (int)S[i].size() - 1; j++)
        {
            if(S[i][j] == 'A' && S[i][j + 1] == 'B')ans++;
        }
        if(S[i][0] == 'B' && S[i][(int)S[i].size() - 1] == 'A')cnt[2]++;
        else if(S[i][0] == 'B')cnt[0]++;
        else if(S[i][(int)S[i].size() - 1] == 'A')cnt[1]++;
    }

    if(cnt[0] == 0 && cnt[1] == 0)cout << ans + max(0, cnt[2] - 1) << endl;
    else cout << ans + min(cnt[0], cnt[1]) + cnt[2] << endl;
    return 0;
}




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

const ll MX = 1e18;

int main() {
    int n;
    cin >> n;
    bool flag = false;

    ll ans = 1;
    rep(i,n) {
        ll a;
        cin >> a;
        if (a == 0) {
            cout << 0 << endl;
            return 0;
        }
        if ((MX+1) / a < ans || ans*a > MX) {
            flag = true;
        }
        ans *= a;
    }
    if (flag == true) {
        cout << -1 << endl;
    } else {
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
#define PI 3.141592653589
#define ll long long
using namespace std;

template<typename T_char>
T_char ToUpper(T_char cX){return toupper(cX);}

int  main(){
  ll n, x;
  cin >> n >> x;
  vector<ll> a(n);
  for(int i=0; i<n; ++i) cin >> a[i];
  sort(a.begin(), a.end());
  int cnt = 0;
  for(int i=0; i<n; ++i){
    if(x>=a[i]) ++cnt, x-=a[i];
    else break;
  }
  if(cnt == n && x) --cnt;
  cout << cnt << endl;
  return 0;
}

Measured memory_bytes: 256
import Data.Char
import qualified Data.List as List

solveAns :: (Int, String) -> String
solveAns (n, str) = fhalf ++ (toLower t) : shalf where
  (fhalf, t : shalf) = List.splitAt (n - 1) str



parseInput :: [[String]] -> (Int, String)
parseInput [[x, y], [r]] = (read y :: Int, r)

main :: IO ()
main =  interact $ solveAns .  parseInput .  map words . lines

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

using namespace std;

int N, M;
int a[100], b[100];

vector<int> Adj[100];

int check[100];

void visit(int M) {
	check[M] = 1;

	for (int i = 0; i < (int)Adj[M].size(); i++) {
		int H = Adj[M][i];
		if (check[H] == 0) { visit(H); }
	}
}

int main(void) {

	cin >> N>>M;

	for (int i = 1; i <= M; i++) {
		cin >> a[i] >> b[i];
	}

	for (int i = 1; i <= M; i++) {
		Adj[a[i]].push_back(b[i]);
		Adj[b[i]].push_back(a[i]);
	}

	int ans = 0;

	for (int i = 1; i <= M; i++) {
		for (int j = 1; j <= N; j++) { check[j] = 0; }
		for (int k = 1; k <= N; k++) { Adj[k].clear(); }
		for (int k = 1; k <= M; k++) {
			if (k == i) { continue; }
			Adj[a[k]].push_back(b[k]);
			Adj[b[k]].push_back(a[k]);
		}

		visit(1);
		bool sign = true;
		for (int k = 1; k <= N; k++) { if (check[k] == 0) { sign = false; } }
		if (!sign) {   ans++; }
	}

	cout << ans << endl;

	//system("pause");
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <unordered_map>
#include <string>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <functional>
using namespace std;
typedef long long int ll;

int main() {
	ll N, x;
	cin >> N >> x;
	vector<ll> a(N);
	for (int i = 0; i < N; ++i) cin >> a[i];
	sort(a.begin(), a.end());

	ll ans = 0;
	ll sum = 0;
	for (; ans < N; ++ans) {
		sum += a[ans];
		if (sum <= x);
		else break;
	}
	if (ans == N && sum < x) --ans;


	cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define maxn (1<<17)+5
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
int n,m;
int a[20];
ll fac[maxn],inv[maxn];
ll dp[20][maxn];
ll quickpow(ll p,ll k)
{
	ll ans=1;
	while(k)
	{
		if(k&1)
			ans=(ans*p)%mod;
		p=(p*p)%mod;
		k>>=1;
	}
	return ans;
}
ll c(ll n1,ll m1)
{
	if(n1<m1) return 0;
	return fac[n1]*inv[m1]%mod*inv[n1-m1]%mod;
}
int getbit(int now)
{
	int res=0;
	while(now)
		res+=(now&1),now>>=1;
	return res;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
		scanf("%d",&a[m-i+1]);
	fac[0]=1;
	for(int i=1;i<=maxn-5;i++)
		fac[i]=fac[i-1]*i%mod;

	inv[maxn-5]=quickpow(fac[maxn-5],mod-2);
	for(int i=maxn-5;i>=1;i--)
		inv[i-1]=inv[i]*i%mod;
	inv[0]=1;

	dp[0][0]=1;

	for(int i=0;i<m;i++)
	{
		for(int state=0;state<(1<<n);state++)
		if(dp[i][state])
		{
			dp[i+1][state]+=dp[i][state];
			dp[i+1][state]%=mod;

			for(int j=0;j<n;j++)
			if(((1<<j)&state)==0)
			{
				dp[i+1][state|(1<<j)]+=(dp[i][state]*fac[(1<<j)]%mod*c((1<<n)-state-a[i+1],(1<<j)-1)%mod);
				dp[i+1][state|(1<<j)]%=mod;
			}
		}
	}

	ll ans=0;
	for(int state=0;state<(1<<n);state++)
	{
		int cnt=getbit(state);
		ll f=(cnt&1)?-1:1;
		ans=(ans+f*dp[m][state]*fac[(1<<n)-state-1])%mod;
	}
	ans=(ans%mod+mod)%mod;
	printf("%lld\n",(ans*(1<<n))%mod);
}

Measured memory_bytes: 18688
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for( int i = 0 ; i < n ; i++ )
 
int main() {
  string S ;
  cin >> S ;
  string W = S ;
  int N = S.size();
  int L_count = 0 ;
  int r_count = 0 ;
  rep(i,N-1){
     if( S[i] == S[i+1] ) {
       L_count++ ;
       if( S[i+1] == '0' ) S[i+1] = '1' ;
       else S[i+1] = '0' ;
    }
  }
    /*for( int i = N - 2 ; i >= 0 ; i-- ){
     if( W[i+1] == W[i] ) {
       r_count++ ;
       if( W[i] == '0' ) W[i] = '1' ;
       else W[i] = '0' ;
    }
  }*/
  cout << L_count << endl;
  //cout << min(L_count,r_count) << endl;
}


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

using namespace std;
using ll =long long;
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define debug(x)  cerr << #x << " = " << (x) << endl;
#define leftunique(a) {sort((a).begin(),(a).end());(a).erase(unique((a).begin(),(a).end()),(a).end());}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
static const ll INF = 1LL << 60;
//Write From this Line

int a[200010],b[200010];
int main()
{
	// input
	int n, k, c;
	string s;
	cin >> n >> k >> c;
	ll ans = 0;
	cin >> s;

	// solve
	int cnt = 0;
	rep(i,n) {
		if(s[i] =='o') {
			a[cnt++] = i;
			i+=c;
		}
	}
	cnt = 0;
	for(int i = n - 1; i >= 0; --i) {
		if(s[i] == 'o') {
			b[cnt++] = i;
			i-=c;
		}
	}

	rep(i, k) {
		if(a[i] == b[k-i-1]) {
			cout << a[i] + 1 << endl;
		}
	}
}


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

#define		maxs(a, b)	a = max(a, b)		//max_self

typedef long long ll;

const int INF = 1e9+5;

int main(){
	ll n, cap;
	scanf("%lld %lld", &n, &cap);	
	vector <ll> w(n);
	vector <ll> v(n);
	for (int i = 0; i < n; ++i){
		scanf("%lld %lld", &w[i], &v[i]);
	}

	vector <ll> dp(cap+1, 0);
	for (int i = 0; i < n; ++i){
		for (int j = cap-w[i]; j >= 0; --j){
			maxs(dp[j+w[i]], dp[j]+v[i]);
		}
	}
	ll ans = 0;
	for (int i = 0; i <= cap; ++i){
		maxs(ans, dp[i]);
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REP2(i, n) for (int i = 1; i <= (int)(n); i++)
#define FOR(i, m, n) for (int i = m; i<n; i++)
#define SORT(x) sort(x.begin(), x.end())
#define REVE(x) reverse(x.begin(), x.end())
#define ALL(x) (x).begin(), (x).end()
#define SUM(x) accumulate(x.begin(), x.end(),0);
#define vint(v,n) vector<int> v(n); REP(i,n) scanf("%lld", &v[i]);
#define vstr(v,n) vector<string> v(n); REP(i,n) scanf("%lld", &v[i]);
struct initon
{
    initon()
    {
        cin.tie(0);
        ios::sync_with_stdio(false);
    };
};
int k=0,n=0, m=0, l=0,r=0,a=0, b=0, c=0, d=0,e=0,ans=0,ans2=0,x=0,y=0;
string s,t,S;
signed main() {
    cin >> s;
    REP(i,s.size()){
         if(s[i]=='A'||s[i]=='C'||s[i]=='G'||s[i]=='T'){
            ans2++;
           ans=max(ans2,ans);
          
            
         }else{
             ans2=0; 
         }
    }
    cout << ans;
}

Measured memory_bytes: 3608
N, M = map(int, input().split())
A = [list(input()) for _ in range(N)]
B = ''
for _ in range(M):
  B += input()

ans = 'No'
for i in range(N-M+1):
  for j in range(N-M+1):
    sbstr = ''
    for k in range(M):
      sbstr += ''.join(A[i+k][j:j+M]) 
    if B == sbstr:
      ans = 'Yes'

print(ans)


Measured memory_bytes: 3060
#include<stdio.h>

int main(){
  int S,h,m,s;
  scanf("%d", &S);
  h = S / 3600;
  m = (S - h * 3600) / 60;
  s = S % 60;
  printf("%d:%d:%d\n",h,m,s);
  return 0;
}


Measured memory_bytes: 2060
import heapq

N,M = map(int,input().split())
s = [list(map(int, input().split())) for _ in range(N)]
jobs = [[] for _ in range(M)]

for i in s:
    if i[0] <= M:
        jobs[i[0]-1].append(-i[1])

condidate=[]
rewards=0
for k in range(M):
    for reward in jobs[k]:
        heapq.heappush(condidate, reward)
    if len(condidate) > 0:
        reward = heapq.heappop(condidate)
        rewards += -reward

print(rewards)

Measured memory_bytes: 39744
solver :: Int -> Int -> Int -> Int -> (Double, Int)
solver w h x y =
  ( (fromIntegral (w * h)) / 2
  , if (w, h) == (2 * x, 2 * y)
      then 1
      else 0)

main :: IO ()
main =
  putStrLn .
  (\(v1, v2) -> show v1 ++ " " ++ show v2) .
  (\(w:h:x:y:_) -> solver w h x y) . map read . words =<<
  getLine


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


int main() {
  int n;
  cin >> n;
  map<int, int> mp;
  int x;
  
  rep(i, n-1){
    cin >> x;
    mp[x]++;
  }
  
  for(int i=1; i<=n; i++) dunk(mp[i]);
  
  return 0;
}


Measured memory_bytes: 12976
#!/usr/bin/env python

contents = []
counter = 0

word = input()

while True:
    text = input()
    if text == "END_OF_TEXT":
        break
    textWords = text.split()
    contents.append(textWords)

for x in contents:
    for y in x:
        if y.lower() == word:
            counter += 1

print(counter)

Measured memory_bytes: 7436
n = int(input())
a = list(map(int,input().split()))
counter = n
prev = [[0,0]]

total = [0]
for i in range(n):
	total.append(total[i]+a[i])

for i in range(n-1):
	k = prev[i][1]+1
	counter += prev[i][1]-i
	cumsum = total[k]-total[i]
	while k <= n-1 and cumsum^a[k] == cumsum+a[k]:
		counter += 1
		cumsum += a[k]
		k += 1
	prev.append([i,k-1])
print(counter)

Measured memory_bytes: 54492
class BIT:
    def __init__(self,n):
        self.size=n
        self.tree=[0]*-~n
    def sum(self,i):
        s=0
        while i:
            s+=self.tree[i]
            i-=i&-i
        return s
    def add(self,i,x):
        while i<=self.size:
            self.tree[i]+=x
            i+=i&-i
def main():
    n=int(input())
    bit=BIT(10**5)
    for a in map(int,input().split()):
        bit.add(a,a)
    for _ in range(int(input())):
        b,c=map(int,input().split())
        t=bit.sum(b)-bit.sum(b-1)
        bit.add(b,-t)
        bit.add(c,t//b*c)
        print(bit.sum(10**5))
main()

Measured memory_bytes: 78928
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc =  new Scanner(System.in);
		int n = sc.nextInt();
		String s = sc.next();

		if ( n%2==1) {
			System.out.println("No");
		} else if (s.length() % 2 == 1){
			System.out.println("No");
		} else {
			int mojisuHalf = n/2;
			String mojiLeft = s.substring(0,mojisuHalf);
			String mojiRight = s.substring(mojisuHalf);
			if (mojiLeft.equals(mojiRight)) {
				System.out.println("Yes");
			} else {
				System.out.println("No");
				}
		}
	}

}


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

// types
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
typedef vector<ll> vll;

// macros
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define FI first
#define SE second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define REP1(i,n) for(int i=1;i<((int)n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define PB push_back
#define EB emplace_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL

// constants
const int inf = 1e9;
const ll linf = 1LL << 50;
const double eps = 1e-10;
const int MOD = 1e9 + 7;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};

#define MAX_N 200

ll colormap[MAX_N];
ll f[MAX_N][MAX_N];
ll n;

bool dfs(ll v, ll c){
  if(colormap[v] == c * -1)
    return false;
  if(colormap[v] == c)
    return true;

  colormap[v] = c;
  REP(i, n){
    if(f[v][i] == 1){
      if(!dfs(i, c*-1))
        return false;
    }
  }
  return true;
}

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  cin >> n;
  vector<string> s(n);
  REP(i,n)
    cin >> s[i];

  //vector<vll> f(n, vll(n));
  REP(i, n){
    colormap[i] = 0;
    REP(j, n){
      f[i][j] = s[i][j] - '0';
      if(f[i][j] == 0 && i != j)
        f[i][j] = inf;
    }
  }


  if(!dfs(0, 1)){
    cout << -1 << endl;
    return 0;
  }

  REP(k, n){
    REP(i, n){
      REP(j, n){
        f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
      }
    }
  }

  ll ans = 0;
  REP(i, n){
    REP(j, n){
      ans = max(ans, f[i][j]);
    }
  }
  cout << ans+1 << endl;

}


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

inline bool is_int(ll x, ll y) {
	bool ok = false;
	if (y / x && !(y % x))
		ok = true;
	return ok;
}

int main() {
	cin.tie(0)->sync_with_stdio(false);

	ll n; cin >> n;

	ll a, b, c;
	a = b = c = 0;
	bool ok = false;
	for (ll i = 1; i <= 3500; i++) {
		for (ll j = 1; j <= 3500; j++) {
			ll x = 4 * i * j - (i + j) * n;
			ll y = i * j * n;
			if (x > 0 && y >= x) {
				if (is_int(x, y)) {
					a = i;
					b = j;
					c = y / x;
					ok = true;
					break ;
				}
			}
		}
		if(ok) break ;
	}

	cout << a << ' ' << b << ' ' << c << '\n';
	return 0;
}

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

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

using LL = long long;
template<class T, size_t D>
struct vec : vector<vec<T, D - 1>> {
  template<class... Args>
  vec(size_t n = 0, Args... args)
    : vector<vec<T, D - 1>>(n, vec<T, D - 1>(args...)) {}
};
template<class T>
struct vec<T, 1> : vector<T> {
  template<class... Args>
  vec(Args... args)
    : vector<T>(args...) {}
};

template<class T>
inline bool asMn(T& a, const T& b) { return a > b ? a = b, true : false; }
template<class T>
inline bool asMx(T& a, const T& b) { return a < b ? a = b, true : false; }
inline int nex(int i, int n) { return i == n - 1 ? 0 : i + 1; }
inline int pre(int i, int n) { return !i ? n - 1 : i - 1; }

const int INF = 1e9;
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());

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

//  freopen("input.txt", "r", stdin);

  string s; cin >> s;
  int n = sz(s); s = ' ' + s;

  vec<int, 2> nxt(n + 2, 26, n + 1);
  for (int i = n - 1; ~i; --i) {
    nxt[i] = nxt[i + 1];
    nxt[i][s[i + 1] - 'a'] = i + 1;
  }

  vec<int, 1> f(n + 2, INF); f[n + 1] = 0;
  for (int i = n; ~i; --i) {
    for (int j = 0; j < 26; ++j) {
      asMn(f[i], f[nxt[i][j]] + 1);
    }
  }

  for (int i = 0, k = f[0]; k; --k) {
    for (int j = 0; j < 26; ++j) {
      if (f[nxt[i][j]] == k - 1) {
        cout << static_cast<char>(j + 'a');
        i = nxt[i][j];
        break ;
      }
    }
  }
  cout << '\n';

  return 0;
}


Measured memory_bytes: 30880
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 2e5 + 5;

int a[N];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin>>n;
	map<int,int>M;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		M[-a[i]-i]++;
	}
	ll ans=0;
	for(int i=1;i<=n;i++){
		if(M.count(a[i]-i)) ans+=M[a[i]-i];
	}
	cout<<ans<<'\n';
	return 0;
}

Measured memory_bytes: 13588
#include <bits/stdc++.h>
using namespace std;
using ll  = long long;
using vl  = vector<ll>;
using vvl = vector<vl>;
#define rep(i,n) for(int i = 0; i < (n); ++i)
const int MAX_N = 2e5+7;

ll N;
vvl G(MAX_N);
vl cs(MAX_N), tree_size(MAX_N), color_cnts(MAX_N,0);
vl ans(MAX_N);

ll nc2(ll x) { return x*(x-1)/2; }

void calc_size(int v, int par = -1) {
    tree_size[v] = 1;
    for (auto to : G[v]) {
        if (to == par) continue;
        calc_size(to, v);
        tree_size[v] += tree_size[to];
    }
}
void dfs(int v, int par = -1) {
    ll prev_cnt = color_cnts[cs[v]];
    for (auto to : G[v]) {
        if (to == par) continue;
        ll prev = color_cnts[cs[v]];
        dfs(to, v);
        ll diff = color_cnts[cs[v]] - prev;
        ll cnt = tree_size[to] - diff;
        cerr << v << "->" << to << ": " << cnt << endl;
        ans[cs[v]] -= nc2(cnt);
    }
    color_cnts[cs[v]] = prev_cnt + tree_size[v];
}

int main() {
    cin >> N;
    ans.assign(MAX_N, nc2(N));
    rep(i,N) cin >> cs[i+1], ans[cs[i+1]]++;
    rep(i,N-1) {
        int u, v; cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    calc_size(1);
    dfs(1);
    rep(c,N) ans[c+1] -= nc2(N-color_cnts[c+1]);
    rep(i,N) cout << ans[i+1] << "\n";
    return 0;
}


Measured memory_bytes: 45236
import java.util.Scanner;

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

        int a = sc.nextInt();
        int b = sc.nextInt();

        if(a == b){
            System.out.println("a == b");
        }
        else if(a < b){
            System.out.println("a < b");
        }
        else {
            System.out.println("a > b");
        }

    }
}



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

using namespace std;

using ll = long long;
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define FORE(i, a, b) for(int i=(a);i<=(b);++i)
#define FORR(i, a, b) for(int i=(b-1);i>=(a);--i)
#define FORRE(i, a, b) for(int i=(b);i>=(a);--i)
#define rep(i, n) for(int i=0;i<(n);++i)
#define repe(i, n) for(int i=0;i<=(n);++i)
#define repr(i, n) for(int i=(n-1);i>=0;--i)
#define repre(i, n) for(int i=(n);i>=0;--i)
#define ALL(v) (v).begin(),(v).end()
#define SP cout<<fixed<<setprecision(10)
typedef pair<int, int> P;
const int INF = (int) 1e9;
const int MOD = (int) 1e9 + 7;

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

int main(void) {
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	ll n, m;
	cin >> n >> m;
	vector<pair<ll, ll>> yenhon;
	rep(i, n) {
		ll a;
		ll b;
		cin >> a >> b;
		yenhon.push_back(make_pair(a, b));
	}
	
	sort(ALL(yenhon));
	
	ll sum = 0;
	for (auto &t: yenhon) {
//		cout << t.first << " " << t.second << endl;
		if (t.second >= m) {
			sum += t.first * m;
			break;
		} else {
			sum += t.first * t.second;
			m -= t.second;
		}
	}
	
	cout << sum << endl;
	
	return 0;
}

Measured memory_bytes: 2420
#include <bits/stdc++.h>
/**
 *    author:  dattrinh
 *    created:    Problemset
**/
#define pb push_back
#define fi first
#define ss second
#define tp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using i64= int64_t;
const int N = 1e4+5;
ll read() {
    char c=getchar();while(!isdigit(c)) c=getchar();
    int num=0;while(isdigit(c)) num=num*10+c-'0',c=getchar();
    return num;
}
/**-----**-----*/
double pi = 3.1605;
ll _;
double x;

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>_;
    x=(2*_)*pi;
    cout<<tp(20)<<x;
    return 0;
}


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

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

    return gcd_ori(b, a % b);
}

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

    string S, T;
    cin >> S >> T;

    if(N==M){
        if(S == T){
            cout << N << endl;
            return 0;
        }
        else{
            cout << -1 << endl;
            return 0;
        }
    }

    if(S.at(0) != T.at(0)){
        cout << -1 << endl;
        return 0;
    }

    ll lcm_n = N * M;
    vector<ll> s(N);
    vector<ll> t(M);

    if(N>M){
        ll tmp = 0;
        tmp = gcd_ori(N, M);
        lcm_n /= tmp;
    }
    else{
        ll tmp = 0;
        tmp = gcd_ori(M, N);
        lcm_n /= tmp;
    }

    for(ll i=0; i<N; i++){
        s.at(i) = 1+lcm_n/N*i;
    }

    for(ll i=0; i<M; i++){
        t.at(i) = 1+lcm_n/M*i;
    }

    if(N>M){
        for(ll i=0; i<M;i++){
            ll l = 0;
            ll r = N-1;
            while(r-l>=0){
                ll mid = (r+l)/2;
                if(t.at(i) == s.at(mid)){
                    if(T.at(i) != S.at(mid)){
                        cout << -1 << endl;
                        return 0;
                    }
                    break;
                }

                if(t.at(i) < s.at(mid)) r = mid - 1;
                if(t.at(i) > s.at(mid)) l = mid + 1;

            }
        }
    }
    else{
        for(ll i=0; i<N;i++){
            ll l = 0;
            ll r = M-1;
            while(r-l>=0){
                ll mid = (r+l)/2;
                if(t.at(mid) == s.at(i)){
                    if(T.at(mid) != S.at(i)){
                        cout << -1 << endl;
                        return 0;
                    }
                    break;
                }

                if(s.at(i) < t.at(mid)) r = mid - 1;
                if(s.at(i) > t.at(mid)) l = mid + 1;

            }
        }        
    }

    cout << lcm_n << endl;

}

Measured memory_bytes: 1792
import java.io.*;
import java.util.*;

 
public class Main{
   public static void main(String[] args) {
      MyScanner sc = new MyScanner();
      out = new PrintWriter(new BufferedOutputStream(System.out));
      String S=sc.next();
      int N=S.length();
      char clst[]=S.toCharArray();
      int curd=1;
      int mod=(int)Math.pow(10, 9)+7;
      int residual[][]=new int[N+1][13];
      residual[0][0]=1;

      for(int dig=1;dig<=N;dig++){
          int p=N-dig;
          char c=clst[p];

          if(c=='?'){
              for(int d=0;d<10;d++){
                  for(int i=0;i<13;i++){
                      residual[dig][(i+d*curd)%13]+=residual[dig-1][i];
                      residual[dig][(i+d*curd)%13]%=mod;
                  }
              }
          }else{
              int d=c-'0';
              for(int i=0;i<13;i++){
                  residual[dig][(i+d*curd)%13]+=residual[dig-1][i];
                  residual[dig][(i+d*curd)%13]%=mod;
              }
          }
          curd=(curd*10)%13;
      }
      out.println(residual[N][5]);
      out.close();
   }

   //-----------PrintWriter for faster output---------------------------------
   public static PrintWriter out;
      
   //-----------MyScanner class for faster input----------
   public static class MyScanner {
      BufferedReader br;
      StringTokenizer st;
 
      public MyScanner() {
         br = new BufferedReader(new InputStreamReader(System.in));
      }
 
      String next() {
          while (st == null || !st.hasMoreElements()) {
              try {
                  st = new StringTokenizer(br.readLine());
              } catch (IOException e) {
                  e.printStackTrace();
              }
          }
          return st.nextToken();
      }
 
      int nextInt() {
          return Integer.parseInt(next());
      }
 
      long nextLong() {
          return Long.parseLong(next());
      }
 
      double nextDouble() {
          return Double.parseDouble(next());
      }
 
      String nextLine(){
          String str = "";
	  try {
	     str = br.readLine();
	  } catch (IOException e) {
	     e.printStackTrace();
	  }
	  return str;
      }
   }
}

Measured memory_bytes: 30488
def read_input():
    a, b, k = map(int, input().split())
    return a, b, k


def submit():
    a, b, k = read_input()

    small_max = a + k - 1
    large_min = b - k + 1

    smalls = list(range(a, small_max + 1))
    larges = list(range(large_min, b + 1))

    result = smalls + larges
    result = list(set(result))
    result.sort()
    for r in result:
        if a <= r <= b:
            print(r)

if __name__ == '__main__':
    submit()


Measured memory_bytes: 3064