akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#define endl "\n"
#define all(V) V.begin( ), V.end( )
#define Unique(V) sort( all( V ) ), V.erase( unique( all( V ) ), V.end() )
#define Check( N , p ) ( !( ( N & ( 1LL << p ) ) == 0 ) )
#define ON( N , p ) ( N = N | ( 1LL << p ) )
#define OFF( N , p ) ( N = N & ~( 1LL << p ) )
std::mt19937 rng( chrono::steady_clock::now().time_since_epoch().count() );
#define rnd(a, b) ((((rand() << 15) ^ rand()) % ((b) - (a) + 1)) + (a))
#define ran(a, b) rng() % ( (b) - (a) + 1 ) + (a)
#define trace(...) __f( #__VA_ARGS__ , __VA_ARGS__ )
template < typename Arg1 >
void __f( const char* name , Arg1&& arg1 ) { cerr << name << " : " << arg1 << "\n"; }
template < typename Arg1 , typename... Args >
void __f( const char* names , Arg1&& arg1 , Args&&... args ) {
const char* comma = strchr( names + 1 , ',' );
cerr.write( names , comma - names ) << " : " << arg1 << " , " ; __f( comma + 1 , args... ); }
typedef long long int LL;
typedef pair <int,int> pii;
typedef pair <long long,long long> pll;
const int MOD = 1e9 + 7;
const double EPS = 1e-8;
const int N = 1e5 + 5;
const int inf = 1e9;
const long long INF = 1e18;

struct DISJOINT_SET_UNION {

        static const int MAXN = 1e5 + 5;

        int Parent[ MAXN ] , Tot[ MAXN ];

        inline void Makeset( int k ) {
                for( int i = 0; i <= k; i++ ) {
                        Parent[ i ] = i; Tot[ i ] = 1;
                }
        }
        inline int Find( int x ) {
                if( Parent[ x ] == x ) return x;
                return Parent[ x ] = Find( Parent[ x ] );
        }
        inline void Union( int x , int y ) {
                int u = Find( x ) , v = Find( y );
                if( u != v ) Parent[ u ] = v , Tot[ v ] += Tot[ u ];
        }
} DSU;

LL calc( LL x ) {
        return x*(x-1)/2;
}
int main( int argc , char const *argv[] ) {
        ios_base::sync_with_stdio( false ); cin.tie( nullptr );
        int n , m;
        cin >> n >> m;
        vector <pii> V;
        LL ans = 1LL*n*(n-1)/2;
        for( int i = 1; i <= m; i++ ) {
                int u , v;
                cin >> u >> v;
                V.push_back( {u,v} );
        }
        DSU.Makeset( n );
        vector <LL> res;
        for( int i = V.size() - 1; i >= 0; i-- ) {
                res.push_back( ans );
                int u = V[i].first , v = V[i].second;
                if( DSU.Find( u ) == DSU.Find( v ) ) continue;
                ans += calc( DSU.Tot[ DSU.Find( V[i].first ) ] );
                ans += calc( DSU.Tot[ DSU.Find( V[i].second ) ] );
                DSU.Union( u , v );
                ans -= calc( DSU.Tot[ DSU.Find( V[i].first ) ] );
        }
        for( int i = res.size() - 1; i >= 0; i-- ) cout << res[i] << endl;
        return 0;
}














Measured memory_bytes: 3828
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <vector>
#include <functional>
using namespace std;

int main() {
  int N,M,C;
  cin >> N >> M >> C;
  int B[M+10];
  for(int j=0; j<M;j++){
    cin >> B[j];
  }
  int sum=0;
  int tmp;
  int counter=0;
  for(int i=0;i<N;i++){
    sum = 0;
    for(int j=0; j<M;j++){
      cin >> tmp;
      sum += tmp*B[j];
    }
    if (sum + C >0) counter++;
  }
  cout << counter << endl;
}


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

int main() {
  int A, B, C, X, Y;
  long long Min=1000000000;
  cin >> A >> B >> C >> X >> Y;
  rep(i, max(X,Y)+1) if(Min>=C*2*i+A*max(0,X-i)+B*max(0,Y-i)) Min=C*2*i+A*max(0,X-i)+B*max(0,Y-i);
  cout << Min << endl;
}

Measured memory_bytes: 256
k = gets.to_i

flg = Array.new(k,false)

now =7%k
i = 0
while i+=1 do
    if now==0 then
        puts i
        return
    end
    break if flg[now]
    flg[now]=true
    now = (now*10+7)%k
end

puts -1

Measured memory_bytes: 22004
def f(S):
  M = {}
  for s in S:
    if s not in M:
      M[s] = chr(ord("a")+len(M))
  return "".join(M[s] for s in S)

S = raw_input()
T = raw_input()
print "Yes" if f(S)==f(T) else "No"


Measured memory_bytes: 4936
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>

#define REP(i, a, b) for (int i = int(a); i < int(b); i++)
#ifdef _DEBUG_
#define dump(val) cerr << __LINE__ << ":\t" << #val << " = " << (val) << endl
#else
#define dump(val)
#endif

using namespace std;

typedef long long int ll;

template<typename T>
vector<T> make_v(size_t a, T b) {
    return vector<T>(a, b);
}
template<typename... Ts>
auto make_v(size_t a, Ts... ts) {
    return vector<decltype(make_v(ts...))>(a, make_v(ts...));
}

#include <utility>
using P = pair<ll, ll>;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<P> A(n);
    REP(i, 0, n) {
        cin >> A[i].second >> A[i].first;
    }
    sort(A.begin(), A.end());
    bool ok = true;
    ll sum = 0;
    REP(i, 0, n) {
        sum += A[i].second;
        if (sum > A[i].first) {
            ok = false;
        }
    }
    cout << (ok ? "Yes" : "No") << endl;

    return 0;
}


Measured memory_bytes: 3456
#include <stdio.h>

int main(void){
    int origSocket, targetSocket, valueStorage = 0, tester = 1;

    scanf("%d %d", &origSocket, &targetSocket);

    while (tester < targetSocket) {
        tester = tester + (origSocket - 1);
        valueStorage++;
    }

    printf("%d\n", valueStorage);

    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define rfor(i, a, b) for(int i = a; i < (int)b; i++)
#define all(ary) (ary).begin(), (ary).end()
#define debug(x) cerr << #x << ": " << x << '\n'
const int INF = 100100100;
const int MOD = 1000000007;
using namespace std;
using vec = vector<int>;
using ll = long long;
template <class T = int> T in(){ T x; cin >> x; return (x);}
const int dy[4] = {-1, 0, 0, 1};
const int dx[4] = {0, -1, 1, 0};

ll n, H;

int main(int argc, char *argv[]){
    cin >> n >> H;
    vector<ll> A(n), B(n);
    rep(i, n){
        cin >> A[i] >> B[i];
    }
    sort(all(A), greater<int>()); sort(all(B), greater<int>());

    ll res = 0;
    for(auto i : B){
        if(H <= 0) break;
        if(i > A[0]){
            res++;
            H -= i;
        }else
            break;
    }
    
    if(H > 0) res += (H + A[0] - 1) / A[0];
    cout << res << endl;
    return 0;
}

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

const int MAXN = 10010;
const int mod = 998244353;
typedef long long LL;
void reduce(int & x) { x += x >> 31 & mod; }
int mul(int a, int b) { return (LL) a * b % mod; }
int pow(int a, int b, int res = 1) {
	for (; b; b >>= 1, a = mul(a, a)) if (b & 1) res = mul(res, a);
	return res;
}
const int MAXS = 20010;
int fac[MAXS], inv[MAXS];
int C(int a, int b) { return (LL) fac[a] * inv[b] % mod * inv[a - b] % mod; }
int down(int a, int b) { return (LL) fac[a] * inv[a - b] % mod; }
int dp[MAXN][MAXN];
char s1[MAXN], s2[MAXN];
int A, B;
int main() {
	fac[0] = fac[1] = inv[0] = inv[1] = 1;
	for (int i = 2; i != MAXS; ++i) {
		fac[i] = mul(fac[i - 1], i);
		inv[i] = mul(inv[mod % i], mod - mod / i);
	}
	for (int i = 2; i != MAXS; ++i) inv[i] = mul(inv[i - 1], inv[i]);
	std::ios_base::sync_with_stdio(false), std::cin.tie(0);
	std::cin >> s1 >> s2; int n = strlen(s1);
	for (int i = 0; i != n; ++i)
		if (s1[i] == '1' && s2[i] == '1') ++A;
		else if (s1[i] == '1' || s2[i] == '1') ++B;
	B >>= 1;
	dp[0][0] = 1;
	for (int i = 0; i <= A; ++i)
		for (int j = 0; j <= B; ++j) {
			reduce(dp[i + 1][j] += mul(dp[i][j], mul(i + 1, j)) - mod);
			reduce(dp[i][j + 1] += mul(dp[i][j], mul(j + 1, j + 1)) - mod);
		}
	int ans = 0;
	for (int i = 0; i <= A; ++i)
		reduce(ans += (LL) dp[i][B] * down(A, A - i) % mod * C(A + B, A - i) % mod * fac[A - i] % mod - mod);
	std::cout << ans << std::endl;
	return 0;
}


Measured memory_bytes: 387712
C = []
for _ in range(3):
    c = list(map(int, input().split()))
    C.append(c)
    
a = [0, C[1][1]-C[0][1], C[2][1]-C[0][1]]
b = [C[0][0], C[0][1], C[0][2]]

ans = [[a[0]+b[0], a[0]+b[1], a[0]+b[2]], [a[1]+b[0], a[1]+b[1], a[1]+b[2]], [a[2]+b[0], a[2]+b[1], a[2]+b[2]]]

if ans == C:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 9168
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
const int INF=1e8;
int main()
{
    int n, m; cin>>n>>m;
    vector<int> g[100010];
    for(int i=0; i<m; i++){
        int u, v; cin>>u>>v; u--; v--;
        g[u].push_back(v);
    }
    int d[3][100010];
    for(int i=0; i<3; i++) fill(d[i], d[i]+n, INF);
    int s, t; cin>>s>>t; s--; t--;
    d[0][s]=0;
    priority_queue<P, vector<P>, greater<P>> que;
    que.push({0, 3*s});
    while(!que.empty()){
        P p=que.top(); que.pop();
        int x=p.second/3, k=p.second%3;
        if(d[k][x]<p.first) continue;
        int a=0;
        if(k==2) a=1;
        int l=(k+1)%3;
        for(auto y:g[x]){
            if(d[l][y]>d[k][x]+a){
                d[l][y]=d[k][x]+a;
                que.push({d[l][y], l+y*3});
            }
        }
    }
    if(d[0][t]==INF) cout<<-1<<endl;
    else cout<<d[0][t]<<endl;
    return 0;
}

Measured memory_bytes: 6912
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = 1e9 + 7;
const ll MAXX = 1e18;  

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//freopen("INP.txt", "r", stdin);
	//freopen("OUT.txt", "w", stdout);
	ll a, b;
	cin >> a >> b;
	ll need = 0;
	ll res = 1;
	while (res < b) {
		res += a - 1;
		need++;
	}
	cout << need << '\n';
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
const int inf = 1e9 + 7;
const ll INF = 1e18;
int mod = 1000000007;
#define abs(x) (x >= 0 ? x : -(x))
#define lb(v, x) (int)(lower_bound(all(v), x) - v.begin())
#define ub(v, x) (int)(upper_bound(all(v), x) - v.begin())
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<typename T> T pow(T a, int b) { return b ? pow(a * a, b / 2) * (b % 2 ? a : 1) : 1; }
ll modpow(ll a, ll b, ll _mod) { return b ? modpow(a * a % _mod, b / 2, _mod) * (b % 2 ? a : 1) % _mod : 1; }
template<class T> ostream& operator << (ostream& os, const vector<T>& vec) { for (auto &vi: vec) os << vi << " "; return os; }
template<class T, class U> ostream& operator << (ostream& os, const pair<T, U>& p) { os << p.F << " " << p.S; return os; }
template<typename T >inline istream& operator >> (istream& is, vector<T>& v) { rep(j, sz(v)) is >> v[j]; return is; }
template<class T> inline void add(T &a, int b) { a += b; if (a >= mod) a -= mod; }


void solve();

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cout << fixed << setprecision(10);

  int T;
  // cin >> T;
  T = 1;

  while (T--) {
    solve();
  }
}

template<typename T>
vector<T> all_divisor_catch(T x) {
  vector<T> v;
  for (T i = 1; i * i <= x; ++i) {
    if (x % i == 0) {
      v.eb(i);
      v.eb(x / i);
    }
  }
  sort(all(v));
  return v;
}

void solve() {
  ll n;
  cin >> n;
  int ans = 0;
  // 最初割り切れるの, 約数しかない
  // 割り切れないなら, mod K = 1
  // N mod K = 1, N-1 mod K = 0
  // N を K ずつ分けたら 1 はみ出る, N-1 ならちょうど
  set<ll> s;
  rep(i, 2) {
    auto v = all_divisor_catch(i == 0 ? n - 1 : n);
    for (auto e : v) s.insert(e);
  }

  for (auto e : s) {
    if (e == 1) continue; // 2 以上
    ll n2 = n;
    while (n2 % e == 0) n2 /= e;
    n2 %= e;
    if (n2 == 1) ans++;
  }
  cout << ans << endl;
}


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

using namespace std;

const int inf = 1 << 29;

vector<vector<int>> floyd_warshall(const vector<vector<int>> &g)
{
	const int n = g.size();
	vector<vector<int>> d = g;
	for (int k = 0; k < n; ++k) {
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
			}
		}
	}
	return d;
}

int main()
{
	int N, M, R;
	cin >> N >> M >> R;
	vector<vector<int>> g(N, vector<int>(N, inf));
	vector<int> r(R);
	for (auto &x : r) {
		cin >> x;
		--x;
	}

	for (int i = 0; i < M; ++i) {
		int A, B, C;
		cin >> A >> B >> C;
		--A;
		--B;
		g[A][B] = g[B][A] = C;
	}

	auto d = floyd_warshall(g);

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

	int ans = 1 << 30;
	do {
		int result = 0;
		for (int i = 1; i < R; ++i) {
			result += d[r[i - 1]][r[i]];
		}
		ans = min(ans, result);
	} while (next_permutation(r.begin(), r.end()));

	cout << ans << endl;
}


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

using namespace std;

#define int long long int
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define se second
#define fi first

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int>> matrix;

const int inf = 1e18;
const int mod = 1e9 + 7;

inline int add(int x, int y) { x += y; if (x >= mod) x -= mod; return x;}
inline int sub(int x, int y) { x -= y; if (x < 0) x += mod; return x;}
inline int mul(int x, int y) { return ((x % mod) * (y % mod)) % mod;}
inline int power(int a, int b) {
    int x = 1;
    while (b) {
        if (b & 1) x = mul(x, a);
        a = mul(a, a);
        b >>= 1;
    }
    return x;
}
inline int inv(int a) { return power(a, mod - 2);}

const int N = 1e5+5;

#undef int
int main() {
#define int long long int
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    clock_t start = clock();

    int n,w; cin>>n>>w;
    vi weight(n+1), value(n+1);
    for(int i=1;i<=n;i++) cin >> weight[i] >> value[i];

    vector<vi> dp(n+1,vi(N,inf));
    dp[0][0]=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<N;j++){
            dp[i][j] = dp[i-1][j];
            if(j-value[i] >= 0) dp[i][j] = min(dp[i][j],weight[i]+dp[i-1][j-value[i]]);
        }
    }

    int ans = 0;
    for(int val=0;val<N;val++){
        if(dp[n][val]<=w) ans=val;
    }
    cout << ans << endl;

    clock_t end = clock();
    cerr << "Time: " << (double)(end - start) / CLOCKS_PER_SEC << " seconds" << endl;

    return 0;
}

Measured memory_bytes: 80256
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0; i<(n); ++i)
using namespace std;
using ll = long long;
using vi = vector<int>;
using vv = vector<vi>;
using P  = pair<int,int>;
const int INF = 1001001001;
const int MOD = 1000000007;

int main(){
    string n;
    cin >> n;
    if(n[n.size()-1]=='s')
        n.push_back('e');
    n.push_back('s');
    cout << n << endl;
    
    return 0;
}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
#define ll  long long int
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
#define M 1000000007
ll factor[1000005];
bool flag=false;    
void fillDivisors(ll x)
{

  if(flag==true)
    return;
  for(int i=1;i*i<=x;i++)
  {
    if(x%i==0)
    {
      ll fact1=i;
      ll fact2=x/i;
      if(fact1==fact2)
      {
        fact1=i;
        fact2=1;
      }

      if(fact1!=1)
      {
        if(factor[fact1])
        {
          flag=true;
          return;
        }
        factor[fact1]++;

      }

      if(fact2!=1)
      {
        if(factor[fact2])
        {
          flag=true;
          return;
        }

        factor[fact2]++;
      }
    }
  }
}


int main()
{

  #ifndef ONLINE_JUDGE


         freopen("input.txt","r",stdin);
         freopen("output.txt","w",stdout); 

 #endif

  fastio;
  ll n;
  cin>>n;
  ll a[n];
  for (int i = 0; i < n; ++i)
   {
      cin>>a[i];
   } 

 

   ll gcd=a[0];
   fillDivisors(a[0]);
   for (int i = 1; i < n; ++i)
   {

      fillDivisors(a[i]);
      gcd=__gcd(gcd,a[i]);
     
   }

   if(!flag)
   {
    cout<<"pairwise coprime";
   }
   else if(gcd==1)
   {
      cout<<"setwise coprime";
   }
   else
    cout<<"not coprime";


  
 


  

return 0;   
}

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

#define int long long
#define INF ((int)1e18)

#define MAX 110000

#define yn(n) ((n)?"Yes":"No")

int median(int a, int b, int c){
  if(a >= b && b >= c || c >= b && b >= a) return b;
  if(b >= a && a >= c || c >= a && a >= b) return a;
  if(a >= c && c >= b || b >= c && c >= a) return c;
  // cout<<a<<endl;
}

int hoge[MAX];

signed main(){
  vector<int> per;
  int N, x;

  cin>>N>>x;

 for(int i = 1; i <= N*2-1; i++) per.push_back(i);

  if(2 <= x && x <= N+(N-2)){
    cout<<"Yes"<<endl;
    
    for(int i = 0; i < N*2-1; i++){
      per[(i+(N*2-1)/2)%(N*2-1)] = (i+x-1+N*2-1)%(N*2-1)+1;
    }
    for(int i = 0; i < N*2-1; i++){
      // if(i)cout<<" ";
      cout<<per[i]<<endl;
    }
    // cout<<endl;
  
    
  } else {
    cout<<"No"<<endl;
  }

  
  return 0;
}


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

#define mp make_pair
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define inf INT_MAX
#define MOD 1000000007
#define fori(i,n) for(int i=0;i<(int)n;++i)
#define forri(i,n) for(int i=n-1;i>=0;--i)
#define forii(i,start,end) for(int i=start;i<end;++i)
#define MEM(a,b) memset(a,(b),sizeof(a))
#define sizearr(arr) sizeof(arr)/sizeof(arr[0])
#define LEN(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define ll long long
#define pll pair<long long,long long>
#define pii pair<int,int>
#define reset(arr, val) fori(i, MAX) arr[i] = val;

#define print(var) cout << var << endl;
#define ENDL cout << endl;
#define coutarr(arr) for(auto a:arr)print(a); ENDL;
#define coutpii(arr) for(pii a:arr)cout << '(' << a.fi << ',' << a.se << ") "; ENDL;
#define cinvec(arr, n) fori(i, n) {int tmp; cin >> tmp; arr.pb(tmp);}
#define cinarr(arr, n) fori(i, n) {int tmp; cin >> tmp; arr[i]=tmp ;}

const int MAX = 1e5 + 5;

vector<int> parent;
vector<int> size_set;

int find_set(int v){
    if (parent[v] == v) return v;
    return parent[v] = find_set(parent[v]);
}

void union_set(int u, int v){
    u = find_set(u);
    v = find_set(v);
    if (u != v){
        if (size_set[u] < size_set[v]){
            int tmpp; tmpp = u; u = v; v = tmpp;
        }
        parent[v] = u;
        size_set[u] += size_set[v];
    }
}

void init_ds(int n){
    for (int i = 0; i < n+1; i++){
        parent.push_back(i);
        size_set.push_back(1);
    }
}


int main(){
	int n, q; cin >> n >> q;
	init_ds(n);
	fori(i, q){
		int com, x, y; cin >> com >> x >> y;
		if (com == 1) cout << (find_set(x) == find_set(y)) << endl;
		else union_set(x, y);
	}
	
	return 0;	
}


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

using namespace std;
using ll = long long;

int main(int argc, const char *argv[]) {
  ll n;
  cin >> n;

  int ans = 0;
  for (int i = 1; i * i <= n; ++i) {
    ans = i * i;
  }

  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 3588
(n, m) = map(int, input().split())
shops = []
for _ in range(n):
    shops.append(list(map(int, input().split())))
shops.sort(key=lambda x: x[0])

num = 0
cost = 0
for shop in shops:
    if (num + shop[1]) >= m:
        cost += shop[0] * (m - num)
        break
    num += shop[1]
    cost += shop[0] * shop[1]
print(cost)


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

int main()
{
    int i,n;
    cin>>n;
    int a[n+2], b[n+2], c[n+2], x=0, y=0, z=0, p, q, r;
    for(i=0;i<n;i++)
    {
        cin>>a[i]>>b[i]>>c[i];
        if(i)
        {
            p=x,q=y,r=z;
            x=a[i]+max(q,r);
            y=b[i]+max(p,r);
            z=c[i]+max(q,p);
        }
        else
        {
            x=a[i], y=b[i], z=c[i];
        }
    }
    cout<<max(x, max(y, z))<<endl;
    return 0;
}


Measured memory_bytes: 1408
n, k = map(int, input().split())
ans = []
for i in range(1, n+1):
    if i < k:
        j = i
        cnt = 0
        while j < k:
            j *= 2
            cnt += 1
        tmp = 1/n * ((1/2) ** cnt)
        ans.append(tmp)
    if i >= k:
        ans.append(1/n)
print(sum(ans))

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

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


Measured memory_bytes: 3900
#include<iostream>
using namespace std;
int main(){ 


  int a,b;

  cin>>a>>b;

  if(a>b){
    cout<<"a > b" <<endl;
      }
  if(a<b){
    cout<<"a < b"<<endl;
      }
  if(a==b){
    cout<<"a == b"<<endl;
      }
  return 0;
}

Measured memory_bytes: 3064
n,m = map(int,input().split())
lis = list(map(int,input().split()))
li = []
for i in range(m):
    a,b = map(int,input().split())
    li.append([b,a])
lis.sort()
li.sort(reverse = True)

num = 0
for cou in range(m):
    for i in range(li[cou][1]):
        try:
            if lis[i+num] < li[cou][0]:
                lis[i+num] = li[cou][0]
            else:
                break
        except:
            break
    num += li[cou][1]
print(sum(lis))

Measured memory_bytes: 24004
import bisect
import sys
input = sys.stdin.readline
from collections import defaultdict
class Bit:
  def __init__(self, n):
    self.size = n
    self.tree = [0] * (n + 1)

  def sum(self, i):
    s = 0
    while i > 0:
        s += self.tree[i]
        i -= i & -i
    return s

  def add(self, i, x):
    while i <= self.size:
      self.tree[i] += x
      i += i & -i
n,d,a = map(int,input().split())
xh = [list(map(int,input().split())) for i in range(n)]
for i in range(n):
  xh[i][1] = (xh[i][1]+a-1)//a
xh.sort()
x = [xh[i][0] for i in range(n)]
remain = [xh[i][1] for i in range(n)]
ans = 0
bit = Bit(n+1)

for i in range(n):
  if bit.sum(i+1) >= remain[i]:
    continue
  br = bisect.bisect_right(x,x[i]+2*d)
  y = remain[i]-bit.sum(i+1)
  ans += y
  bit.add(i+1,y)
  bit.add(br+1,-y)
print(ans)

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

int main(){
    ll n, h, w;
    cin >> w >> h >> n;
    ll ux = w, bx = 0, uy = h, by = 0;
    rep(i, 0, n){
        ll x, y, a;
        cin >> x >> y >> a;
        if(a == 1){
            bx = max(bx, x);
        }
        if(a == 2){
            ux = min(ux, x);
        }
        if(a == 3){
            by = max(by, y);
        }
        if(a == 4){
            uy = min(uy, y);
        }
        // cerr << bx << "," << ux << endl;
        // cerr << by << "," << uy << endl;
    }
    ll ans;
    if(bx > ux || by > uy) ans = 0;
    else ans = (ux - bx) * (uy - by);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3604
#include <stdio.h>
#define SIZE 110
#define INF 1000000009

int dp[SIZE][SIZE];
int in[SIZE];

int min(int a, int b){
  return (a<b ? a : b);
}

int main(){
  int n,i,j,k;
  scanf("%d",&n);
  for(i=1; i<=n; i++){
    scanf("%d %d",&in[i-1],&in[i]);
  }
  
  for(i=1; i<=n; i++) dp[i][i] = 0;
  
  for(k=2; k<=n; k++){
    for(i=1; i<=n-k+1; i++){
      int v;
      v = i+k-1;
      dp[i][v] = INF;
      for(j=i; j<=v-1; j++){
        dp[i][v] = min(dp[i][v],dp[i][j]+dp[j+1][v]+in[i-1]*in[j]*in[v]);
      }
    }
  }
  
  printf("%d\n",dp[1][n]);
  
  return 0;
}



Measured memory_bytes: 2148
sx,sy,tx,ty = map(int,input().split())
diff_x = tx-sx
diff_y = ty-sy
ans = []
for i in range(diff_x):
    ans.append("R")
for j in range(diff_y):
    ans.append("U")
for i in range(diff_x):
    ans.append("L")
for j in range(diff_y):
    ans.append("D")
ans.append("D")
for i in range(diff_x+1):
    ans.append("R")
for j in range(diff_y+1):
    ans.append("U")
ans.append("L")
ans.append("U")
for i in range(diff_x+1):
    ans.append("L")
for j in range(diff_y+1):
    ans.append("D")
ans.append("R")
print("".join(ans))




Measured memory_bytes: 40176
#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include<iostream>
#include<string>
#include <vector>

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

using namespace std;

int main(){
	int N, A[100], v, j;

	scanf("%d", &N);
	REP(i, N){
		scanf(" %d", &A[i]);
	}

	FOR(i,1, N){

		REP(k, N - 1){
			printf("%d ", A[k]);
		}
		printf("%d\n", A[N - 1]);

		v = A[i];
		j = i - 1;
		while (j >= 0 && A[j] > v){
			A[j + 1] = A[j];
			j--;
		}
		A[j + 1] = v;
	}

	REP(k, N - 1){
		printf("%d ", A[k]);
	}
	printf("%d\n", A[N - 1]);

	return 0;
}


Measured memory_bytes: 3192
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

typedef long long ll;

const ll MAX_N = 1e5+10;

ll gcd(ll x, ll y){
  if(y == 0) return x;
  return gcd(y,x%y);
}

int main(int argc, char const *argv[])
{
    ll n, a[MAX_N];
    vector<ll> fvec(MAX_N), bvec(MAX_N), gcd_vec;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        scanf("%lld", &a[i]);
    }
    fvec[1] = a[0];
    bvec[n-2] = a[n-1];
    for (int i = 1; i < n-1; ++i) {
        fvec[i+1] = gcd(fvec[i], a[i]);
    }

    for (int i = n-2; i > 0; --i) {
        bvec[i-1] = gcd(bvec[i], a[i]);
    }

    for (int i = 0; i < n; ++i) {
        if (i==0) {
            gcd_vec.emplace_back(bvec[0]);
        }
        else if (i==n-1) {
            gcd_vec.emplace_back(fvec[n-1]);
        }
        else {
            gcd_vec.emplace_back(gcd(fvec[i], bvec[i]));
        }
    }


    sort(gcd_vec.rbegin(), gcd_vec.rend());
    
    cout << gcd_vec[0] << endl;



    return 0;
}

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

ret = [float('inf')] * (1 << N)
for _ in range(M) :
    a, b = map(int, input().split())
    c = 0
    for i in input().split() :
        c |= 1 << (int(i) - 1)
    ret[c] = min(ret[c], a)

for i in range(1 << N) :
    if ret[i] == float('inf') :
        continue
    for j in range(1 << N) :
        k = i | j
        ret[k] = min(ret[k], ret[i] + ret[j])

if ret[-1] == float('inf') :
    print(-1)
else :
    print(ret[-1])

Measured memory_bytes: 47320
import java.util.Scanner;

public class Main {
    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int h[] = new int[n];
        for (int i = 0; i < n; i++) {
            h[i] = in.nextInt();
        }
        int prev1_cost = 0;
        int prev2_cost = 0;
        for (int  i = 1; i < n; i++) {
            int temp = prev1_cost;
            prev1_cost = prev1_cost + Math.abs(h[i] - h[i-1]);
            prev2_cost = prev2_cost + Math.abs(h[i] - ((i-2 >= 0)?h[i-2]:Integer.MAX_VALUE));
            prev1_cost = Math.min(prev1_cost, prev2_cost);
            prev2_cost = temp;
        }
        System.out.println(prev1_cost);
    }
}


Measured memory_bytes: 52628
while True:
    h,w = map(int,input().split())
    if h==0 and w==0:
        break
    for i in range(h):
        if i%2==0:
            if w%2==0:
                print('#.'*int(w/2))
            else:
                print('#.'*int(w/2)+'#')
        if i%2!=0:
            if w%2==0:
                print('.#'*int(w/2))
            else:
                print('.#'*int(w/2)+'.')
    print()


Measured memory_bytes: 5612
a, b, c = map(int, input().split())
print(max(a + (b*10+c), (a*10+b) + c,
a + (c*10+b), (a*10+c) + b,
b + (a*10+c), (b*10+a) + c,
b + (c*10+a), (b*10+c) + a,
c + (a*10+b), (c*10+a) + b,
c + (b*10+a), (c*10+b) + a))



Measured memory_bytes: 38256
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <cmath>
#include <iomanip>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cassert>
#include <cstring>
#include <climits>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define rep(i, n) FOR(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())
#define INF (ll)1e18
#define MOD (ll)1e9 + 7
#define pb push_back

typedef long long ll;
typedef long long int llt;
typedef pair<int, int> P;
typedef vector<int> V;
typedef map<int, int> M;

char dif = 'A' - 'a';
int mod = 1e9 + 7;
ll inf = 1e18;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, q, l[112345], r[112345];
    string s;
    cin >> n >> q >> s;
    for (int i = 0; i < q; i++){
        cin >> l[i] >> r[i];
    }
    vector<int> a(n);
    a[0] = 0;
    for (int i = 1; i < n; i++){
        if(s[i-1]=='A'&&s[i]=='C'){
            a[i] = a[i - 1] + 1;
        }
        else
            a[i] = a[i - 1];
    }
    for (int i = 0; i < q;i++){
        if(l[i]==1){
            cout << a[r[i] - 1] << endl;
        }
        else
            cout << a[r[i] - 1] - a[l[i] - 1] << endl;
    }
    return 0;
}

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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rrep(i, n) for(int i = ((int)(n)-1); i >= 0; i--)
#define all(x) (x).begin(),(x).end()

using namespace std;
using ll = long long;

struct edge { int to, cost; };

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> P;
 
const int INF = 1e9;
//const ll INF = 1e18;
const double EPS = 1e-10;
const int MOD = 1e9+7;
const double PI = acos(-1.0);

int main()
{
	char b;
	cin >> b;
	if(b == 'A') cout << 'T' << endl;
	if(b == 'T') cout << 'A' << endl;
	if(b == 'C') cout << 'G' << endl;
	if(b == 'G') cout << 'C' << endl;
	return 0;	
}

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner io = new Scanner(System.in);
		int N = io.nextInt();
		int A = io.nextInt();
		int B = io.nextInt();
		Long[] v = new Long[N];
		for (int i = 0; i < N; i++) {
			v[i] = io.nextLong();
		}
		Arrays.sort(v,Collections.reverseOrder());
		
		long sum = 0;
		long pair = 0;
		
		long now = -1;
		int seq = 0;
		for(int i=0;i<A;i++){
			sum += v[i];
			if(now != v[i]){
				now = v[i];
				seq = 1;
			}else{
				seq ++;
			}
		}
		int after = 0;
		for(int i=A;i<N;i++){
			if(now!=v[i]) break;
			else after ++;
		}
		
		if(now!=v[0]){
			pair = comp(seq+after,seq);
		}else{
			for(int i=A;i<=Math.min(B,seq+after);i++){
				pair += comp(seq+after,i);
			}
		}
		
		System.out.println(sum/((double)A));
		System.out.println(pair);
	}
	
	public static long[][] map = new long[51][51];
	
	public static long comp(int a,int b){
		
		if(map[a][b]!=0) return map[a][b];
		long ans = 0;
		if(b==0 || b==a){
			ans = 1;
		}else{
			ans = comp(a-1,b-1)+comp(a-1,b);
		}
		map[a][b] = ans;
		return ans;
	}
}	

Measured memory_bytes: 23764
#include<iostream>

using namespace std;

int main() {
	int h, w, k;
	cin >> h >> w >> k;
	string* c = new string[h];
	for (int i = 0;i < h;i++) {
		cin >> c[i];
	}
	int ans = 0;
	for (int i = 0;i < 1 << h;i++) {
		for (int j = 0;j < 1 << w;j++) {
			int kosuu = 0;
			for (int i1 = 0;i1 < h;i1++) {
				if (i & 1 << i1)continue;
				for (int j1 = 0;j1 < w;j1++) {
					if (j & 1 << j1)continue;
					if (c[i1][j1] == '#')kosuu++;
				}
			}
			if (kosuu == k)ans++;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 3188
X, Y = map(int, input().split())

sumPriz = 0

if X == 1:
    sumPriz += 300000
elif X == 2:
    sumPriz += 200000
elif X == 3:
    sumPriz += 100000

if Y == 1:
    sumPriz += 300000
    if X == 1:
        sumPriz += 400000
elif Y == 2:
    sumPriz += 200000
elif Y == 3:
    sumPriz += 100000

print(sumPriz)

Measured memory_bytes: 3060
#include <iostream>
#include <cstdio>
#include <vector>
#define N 100005
using namespace std;

int n, m, a, b, c[N], d[N];
vector<int> gr[N];

void f(int p, int q) {
	d[p] = d[q] + 1;
	for(auto x:gr[p]) {
		if(x == q) continue;
		if(d[x]) {
			if(d[x] < d[p]) {
				c[p] ^= 1;
				printf("%d %d\n", p, x);
			}
		} else {
			f(x, p);
		}
	}
	if(c[p]) printf("%d %d\n", p, q);
	else if(q) {
		c[q] ^= 1;
		printf("%d %d\n", q, p);
	}
}

int main() {
	cin >> n >> m;
	if(m&1) return puts("-1")*0;
	while(m--) {
		scanf("%d%d", &a, &b);
		gr[a].push_back(b);
		gr[b].push_back(a);
	}
	f(1, 0);
	return 0;
}

Measured memory_bytes: 13952
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main(void) {
	int h[20];
	for (int i = 0; i < 10; i++) {
		cin >> h[i];
	}
	sort(h, h + 10);
	for (int i = 9; i > 6; i--) {
		cout << h[i] << endl;
	}
	return 0;
}

Measured memory_bytes: 3136
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
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; }
using ll = long long;
const ll MOD = 1e9+7; int INF=INT_MAX; ll LLINF = 1LL << 60;
const vector<int> d8x = {1, 0, -1, 0, 1, -1, -1, 1}; vector<int> d8y = {0, 1, 0, -1, 1, 1, -1, -1};
const vector<int> d4x = {1, 0, -1, 0}; vector<int> d4y = {0, 1, 0, -1};

//

int main(){
    int n; cin>>n;
    vector<vector<int>> happy(n, vector<int>(3));
    rep(i,n){
        rep(j,3){
            cin>>happy[i][j];
        }
    }
    vector<vector<int>> dp(n,vector<int>(3,-1));
    rep(i,3){
        dp[0][i]=happy[0][i];
    }
    for (int i = 1; i < n; i++)
    {
        rep(j,3){
            rep(k,3){
                if(j!=k) chmax(dp[i][j], dp[i-1][k]+happy[i][j]);
            }
        }
    }
    cout<<max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]))<<endl;
}

Measured memory_bytes: 11136
# -*- coding: utf-8 -*-

"""
参考：https://ikatakos.com/pot/programming_algorithm/graph_theory/bipartite_matching
・二部最大マッチング
"""

class BipartiteMatching:
    """
    XとYの二部グラフの最大マッチング X={0,1,2,...|X|-1} Y={0,1,2,...,|Y|-1}
    edges[x]: xとつながるYの頂点のset
    match1[x]: xとマッチングされたYの頂点
    match2[y]: yとマッチングされたXの頂点
    """

    def __init__(self, n, m):
        self.n = n
        self.m = m
        self.edges = [set() for _ in range(n)]
        self.match1 = [-1] * n
        self.match2 = [-1] * m
 
    def dfs(self, v, visited):
        """
        :param v: X側の未マッチングの頂点の1つ
        :param visited: 空のsetを渡す（外部からの呼び出し時）
        :return: 増大路が見つかればTrue
        """
        for u in self.edges[v]:
            if u in visited:
                continue
            visited.add(u)
            if self.match2[u] == -1 or self.dfs(self.match2[u], visited):
                self.match2[u] = v
                self.match1[v] = u
                return True
        return False
    
    def add(self, a, b):
        self.edges[a].add(b)

    def whois1(self, a):
        """ :param: グループ1の頂点 :return: ペアになるグループ2の頂点 """
        return self.match1[a]

    def whois2(self, a):
        """ :param: グループ2の頂点 :return: ペアになるグループ1の頂点 """
        return self.match2[a]

    def solve(self):
        # 増大路発見に成功したらTrue(=1)。合計することでマッチング数となる
        return sum(self.dfs(i, set()) for i in range(self.n))


N = int(input())
aN, bN, cN, dN = [0] * N, [0] * N, [0] * N, [0] * N
# 赤い点
for i in range(N):
	aN[i], bN[i] = map(int, input().split())
# 青い点
for i in range(N):
	cN[i], dN[i] = map(int, input().split())

# (赤い点の数, 青い点の数)
bm = BipartiteMatching(N, N)
for i in range(N):
	for j in range(N):
		if aN[i] < cN[j] and bN[i] < dN[j]:
			# ペア候補として適切な組を追加していく(0-indexed)
			bm.add(i, j)
print(bm.solve())


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

ll solve(ll x){
    ll ans = 0;
    if(x%2 == 0){
        ans = (x+1)^solve(x+1);
    }else{
        ans = (x+1)/2 % 2;
    }
    return ans;
}

int main(){
    ll A,B;
    cin >> A >>B;
    ll ans = solve(B)^solve(A-1);
    cout<<ans<<endl;    
    return 0;
}

Measured memory_bytes: 256
while True:
    count = 0
    n, x = map(int, input().split())
    if n == 0 and x == 0:
        break
    for i in range(1, n+1):
        for j in range(i+1, n+1):
            for k in range(j+1, n+1):
                if i + j + k == x:
                    count += 1
    print(count)



Measured memory_bytes: 5596
while True:
    n = input()
    if n == 0:
        break
    ATen = 0
    BTen = 0
    for i in range(n):
        A, B = map(int, raw_input().split())
        if A > B:
            ATen += A + B
        elif A < B:
            BTen += A + B
        elif A == B:
            ATen += A
            BTen += B
    print ATen, BTen

Measured memory_bytes: 6592
#include <stdio.h>

int main(void) {
  int n, k;
  scanf("%d %d", &n, &k);
  int array[n];

  int i, j, tmp;
  for (i = 0; i < n; i++) {
        scanf("%d", &tmp);
        array[i] = tmp;
  }

  for (i = 0; i < n; i++) {
        for (j = 0; j < n - i - 1; j++) {
          if (array[j] > array[j + 1]) {
                tmp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = tmp;
          }
        }
  }

  int sum;
  sum = 0;
  for (i = 0; i < k; i++) {
        sum += array[n - i - 1];
  }

  printf("%d\n", sum);

  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define REP(i, n) for (ll i = 0; i < n; ++i)

using namespace std;
using ll = long long;

void solve(ll N, vector<ll> A) {
  ll ans(0);
  REP(i, N - 1)
    if (A[i] > A[i + 1]) {
      ans += A[i] - A[i + 1];
      A[i + 1] = A[i];
    }
  cout << ans << endl;
}

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

  ll N;
  cin >> N;
  vector<ll> A(N);
  REP(i, N)
    cin >> A[i];

  solve(N, move(A));

  return 0;
}


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

int main()
{
        int a[3], diff1, diff2, ans;
        cin >> a[0] >> a[1] >> a[2];
	    sort(a, a+3);
        diff1 = a[2] - a[0];
        diff2 = a[2] - a[1];
        if(diff1%2 == 0 && diff2%2 == 0) {
                ans = diff1/2 + diff2/2;
        } else if(diff1%2 == 1 && diff2%2 == 1) {
                ans = diff1/2 + diff2/2 + 1;
        } else {
                ans = diff1/2 + diff2/2 + 2;
        }
        cout << ans << endl;
	return 0;
}

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

int main() {
  string S;
  int K;
  int64_t Q=998244353;
  cin>>S>>K;
  vector<int> p;
  int a=0,A=0,V=S.size();
  for(int i=0;i<V;i++){
    if(S.at(i)=='1'){
      a++;
      A++;
    }
    else{
      p.push_back(a);
      a=0;
    }
  }
  int N=p.size();
  K=min(K,A);
  
  vector dp(K+1, vector(K+1, vector(N+1, 0L))), yr = dp, tr = dp;
  
  dp[0][0][0]=1;
  for(int i=0;i<N;i++){
    for(int j=0;j<=K;j++){
      yr[j][j][i]=dp[j][j][i];
      tr[K-j][0][i]=dp[K-j][0][i];
      for(int k=j;k<K;k++){
        yr[k+1][j][i]=(yr[k][j][i]+dp[k+1][j][i])%Q;
        tr[K-j][k+1-j][i]=(tr[K-j][k-j][i]+dp[K-j][k+1-j][i])%Q;
      }
    }
    int B=p[i];
    for(int j=0;j<=K;j++){
      for(int k=0;k<=j;k++){
        int64_t X=0,Y=0;
        if(k-B-1>=0){
          X=tr[j][k-B-1][i];
        }
        if(j-A+B-1>=0){
          Y=yr[j-A+B-1][k][i];
        }
        dp[j][k][i+1]=(tr[j][k][i]+yr[j][k][i]-dp[j][k][i]-X-Y+3*Q)%Q;
      }
    }
  }
  int64_t Z=0;
  for(int j=0;j<=K;j++){
    for(int i=j;i<=min(K,j+a);i++){
      Z+=dp[i][j][N];
      Z%=Q;
    }
  }
  cout<<Z<<endl;
}

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

using namespace std;

int main(){
  int A;
  int B;
  int M;
  cin >> A >> B >> M;
  vector<int> a(A);
  vector<int> b(B);
  vector<int> ans;

  for(int i=0;i<A;i++){
    cin >> a.at(i);
  }
  for(int i=0;i<B;i++){
    cin >> b.at(i);
  }
  for(int i=0;i<M;i++){
    int x;
    int y;
    int c;
    cin >> x >> y >> c;
    ans.push_back(a.at(x-1) + b.at(y-1) - c);
  }
  sort(a.begin(), a.end());
  sort(b.begin(), b.end());

  ans.push_back(a.at(0)+b.at(0));

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

  cout << ans.at(0) << endl;

  return 0;
}


Measured memory_bytes: 1660
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] t = new int[n];
        sc.nextLine();
        int sum = 0;
        for(int i = 0;i<n;i++){
            t[i] = sc.nextInt();
            sum += t[i];
        }
        sc.nextLine();
        int m = sc.nextInt();
        int tmp = 0;
        int[] answer = new int[m];
        for(int i = 0;i<m;i++){
            tmp = sum;
            tmp -= t[sc.nextInt()-1];
            tmp += sc.nextInt();
            sc.nextLine();
            answer[i] = tmp;
        }
        for(int i = 0;i<m;i++){
            System.out.println(answer[i]);
        }
    }
}

Measured memory_bytes: 23636
n = int(input())
lists = list(map(int, input().split()))
a = 0

for x in lists:
    for y in lists:
        for z in lists:
            if x + y > z and x + z > y and y + z > x and x < y and y < z:
                a += 1
               
            else:
                continue
               
            
print(a)

Measured memory_bytes: 9136
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<cmath>
using namespace std;
int main(){
long long int in;
while(cin>>in,in+1){
double x=in/2;
while(x*x*x-in>0.00001*in||x*x*x-in<-0.00001*in)
x-=(x*x*x-in)/(3*x*x);
if(in!=1)
printf("%.6f\n",x);
else
cout<<1<<endl;
}
}

Measured memory_bytes: 1236
N, M = map(int, input().split())
ac = 0
wa = 0
mp = [0]*N
for _ in range(M):
    p, S = input().split()
    p = int(p) - 1
    if S == "AC":
        if mp[p] != "AC":
            ac += 1
            wa += mp[p]
            mp[p] = "AC"
    else:
        if mp[p] != "AC":
            mp[p] += 1
print(ac, wa)

Measured memory_bytes: 3828
N = int(input())


def dist(i, j):
    return i + j - 2


min = 10 ** 24
i = 1
while (i ** 2) <= N:
    if 0 == N % i:
        j = N // i
        d = dist(i, j)
        if min > d:
            min = d
    i += 1
print(d)


Measured memory_bytes: 2940
#include<iostream>
int n,t,x,y,pt,px,py,f,d;
int main(){
	std::cin>>n;
	for(;n--;pt=t,px=x,py=y)std::cin>>t>>x>>y,d=abs(x-px)+abs(y-py),f=(t-pt<d||(d-t+pt)%2)?1:0;
	std::cout<<(f?"No":"Yes");
}

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

int N;

int main() {
	cin >> N;
	int ans = 0;
	rep(i, N) {
		int tmp;
		cin >> tmp;
		tmp--;
		ans += tmp;
	}
	cout << ans << endl;
}

Measured memory_bytes: 3608
#include <iostream>
#include <cstdlib>
int main(int argc, char** argv)
{
    using namespace std;
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    cout << (abs(a - c) > d && (abs(a - b) > d || abs(c - b) > d) ? "No" : "Yes");
    return 0;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
#define int long long
#ifndef FAST_IO
  #define IOS ios_base::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
#endif
#define ff first
#define ss second
#define endl "\n"
#define all(c) c.begin(),c.end()
template<typename T>void print(T t){for(auto &it:t)cout<<it<<" "; cout<<endl;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void solve(){
   int n;
   cin>>n;
   vector<pair<int,int> >v;
   for(int i=0;i<n;i++){
	     int l,r;
	     cin>>l>>r;
	     v.emplace_back(make_pair(l,r)); 
	  }
	  int ans=0;
	  for(auto it:v){
		  ans+=(it.second-it.first+1);
		 }
	cout<<ans<<endl;
}
int32_t main(){
   IOS;
   solve();
   //debug();
  #ifdef LOCAL_DEFINE
   cerr<<"time elapsed "<<(double)clock()/CLOCKS_PER_SEC<<endl;
  #endif	
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <utility>
#include <queue>
using namespace std;
typedef long long ll;

const int INF = 1000000000;

int main()
{
    int n, m, p;
    cin >> n >> m >> p;
    ll a[5002], b[5002], c[5002];
    vector<int> rev[5002];
    for(int i = 0; i < m; i++){
        cin >> a[i] >> b[i] >> c[i];
        rev[b[i]].push_back(a[i]);
        c[i] -= p;
    }
    bool arrival[2502];
    for(int i = 1; i <= n; i++) arrival[i] = false;
    arrival[n] = true;
    queue<int> que;
    que.push(n);
    while(!que.empty()){
        int now = que.front();
        que.pop();
        for(int next : rev[now]){
            if(!arrival[next]){
                arrival[next] = true;
                que.push(next);
            }
        }
    }
    ll d[2502];
    for(int i = 1; i <= n; i++) d[i] = -INF;
    d[1] = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(d[a[j]] != -INF && d[b[j]] < d[a[j]] + c[j]) d[b[j]] = d[a[j]] + c[j];
        }
    }
    ll memo[2502];
    for(int i = 1; i <= n; i++){
        memo[i] = d[i];
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(d[a[j]] != -INF && d[b[j]] < d[a[j]] + c[j]) d[b[j]] = d[a[j]] + c[j];
        }
    }
    bool inf = false;
    for(int i = 1; i <= n; i++){
        if(d[i] != memo[i] && arrival[i]) inf = true;
    }
    ll zero = 0;
    if(inf) cout << -1 << endl;
    else cout << max(d[n], zero) << endl;
}

Measured memory_bytes: 640
#include<iostream>
#include<string>
using namespace std;
struct dice
{
	int s[6], b;
	void roll(char c)
	{
		if (c == 'W')
		{
			b = s[0];
			s[0] = s[2];
			s[2] = s[5];
			s[5] = s[3];
			s[3] = b;
		}
		if (c == 'E')
		{
			b = s[0];
			s[0] = s[3];
			s[3] = s[5];
			s[5] = s[2];
			s[2] = b;
		}
		if (c == 'S')
		{
			b = s[0];
			s[0] = s[4];
			s[4] = s[5];
			s[5] = s[1];
			s[1] = b;

		}
		if (c == 'N')
		{
			b = s[0];
			s[0] = s[1];
			s[1] = s[5];
			s[5] = s[4];
			s[4] = b;
		}
		if (c == 'R')
		{
			b = s[1];
			s[1] = s[2];
			s[2] = s[4];
			s[4] = s[3];
			s[3] = b;
		}
	}
	int top()
	{
		return s[0];
	}
	int left()
	{
		return s[3];
	}
	int right()
	{
		return s[2];
	}
	int front()
	{
		return s[1];
	}
};

bool same(int a[],int b[])
{
	for (int i = 0; i < 6; i++)
		if (a[i] != b[i])return false;
	return true;
}

int main()
{
	dice d, ano;
	int i,j;
	for (int i = 0; i < 6; i++)
	{
		cin >> d.s[i];
	}
	for (int i = 0; i < 6; i++)
	{
		cin >> ano.s[i];
	}
	bool sam = false;

	for (i = 0; i < 4; i++)
	{
		ano.roll('R');
		for (j = 0; j < 4; j++)
		{
			ano.roll('N');
			if (same(d.s, ano.s))sam = true;
		}
	}
	ano.roll('E');
	for (j = 0; j < 4; j++)
	{
		ano.roll('N');
		if (same(d.s, ano.s))sam = true;
	}
	ano.roll('W');
	ano.roll('W');
	for (j = 0; j < 4; j++)
	{
		ano.roll('N');
		if (same(d.s, ano.s))sam = true;
	}

	cout << (sam ? "Yes" : "No") << endl;
	return 0;
}



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

int main() {
  ll a,b,n;
  cin>>a>>b>>n;
  ll p=(a*min(b-1,n))/b;
  ll q=((min(b-1,n)/b))*a;
  cout<<p-q<<endl;
}

Measured memory_bytes: 3636
mod = 10 ** 9 + 7
class nCr():
    def __init__(self, n):
        self.n = n
        self.fa = [1] * (self.n + 1)
        self.fi = [1] * (self.n + 1)
        for i in range(1, self.n + 1):
            self.fa[i] = self.fa[i - 1] * i % mod
            self.fi[i] = pow(self.fa[i], mod - 2, mod)
    def comb(self, n, r):
        if n < r:return 0
        if n < 0 or r < 0:return 0
        return self.fa[n] * self.fi[r] % mod * self.fi[n - r] % mod
n, m, k = map(int, input().split())
ans = 0
c = nCr(n * m)
for i in range(n):
    ans += i * (n - i) * m * m
    ans %= mod
for i in range(m):
    ans += i * (m - i) * n * n
    ans %= mod
print(ans * c.comb(n * m - 2, k - 2) % mod)

Measured memory_bytes: 24532
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    long D = sc.nextLong();
    long X = 0;
    long Y = 0;
    int ans = 0;
    
    for(int i = 0; i < N; ++i) {
      X = sc.nextLong();
      Y = sc.nextLong();
      if((X * X + Y * Y) <= D * D) {
          ++ans;
      }
    }
    System.out.println(ans);
  }
}

Measured memory_bytes: 60576
N=int(input())
S=[str(input()) for i in range(N)]

AC=S.count("AC")
WA=S.count("WA")
TLE=S.count("TLE")
RE=S.count("RE")

print(f"AC x {AC}")
print(f"WA x {WA}")
print(f"TLE x {TLE}")
print(f"RE x {RE}")

Measured memory_bytes: 16192