akhauriyash/Code-Regression huggingface dataset:
#include <string>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream> 
#include <cmath>
#include <map>
#include <queue>
 
using namespace std;
typedef long long ll;
typedef long double ld;
 
const ll MOD=ll(1e9+7);
 
//repetition
#define REP(i,n)  for(ll i=0;i<n;i++)
 
ll P_POW(ll i, ll n) {
  if(n==0) return 1;
 
  n--;
  ll rep = i;
 
  while(n) {
    rep = rep * i;
    n--;
  }
  return rep;
} 
 
unsigned GetDigit(unsigned num){
    unsigned digit=0;
    while(num!=0){
        num /= 10;
        digit++;
    }
    return digit;
}
 
unsigned binarySearch(ll target, ll max, ll min) {
  while((max - min) > 1) {
      if((max + min)/2 > target) {
        max = (max + min)/2;
        min = min;
      } else {
        max = max;
        min = (max + min)/2;
      }
    }
}
 
ll n;
 
 
long long solve2(long long N) {
    if (N % 2 == 1) return 0;
 
    long long res = 0;
    N /= 2;
    while (N) {
        res += N / 5;
        cout << "N/5: " << N/5 <<  endl;
        cout << "res1: " << res <<  endl;
        N /= 5;
    }
    return res;
}
 
 
ll solve(ll n) {
    if (n % 2 == 1) return 0;
 
    ll res = 0;
    n /= 2;
    int c = 1;
 
    while ((ll) n/((ll)pow(5,c))) {
      res += n/P_POW(5,c);
      c++;
    }
    return res;
}
 
void f(int rest, string s) {
  char abc[] = "abc";
  if(rest == 0) {
    cout << s << endl;
  } else {
    for(int i=0; i < 3; i++) {
      f(rest - 1, s+abc[i]);
    }
  }
} 

int main() {
  ll a, n;
  cin >> n;
  // 2次元vector
  // vector<vector<ll>> a(n ,vector<ll>{2,0});
  // vector
  // vector<ll> s(n,0);
  // vector<vector<ll>> v;
  // map<ll,ll> m;
  // priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;

  vector<ll> ev(n+10);
  vector<ll> ov(n+10);

  map<ll, ll> em;
  map<ll, ll> om;

  vector<pair<ll, ll>> epv;
  vector<pair<ll, ll>> opv;

  REP(i, n) {
    cin >> a;
    if(i%2 == 0) {
      em[a]++;
    } else {
      om[a]++;
    }
  }

  REP(i, 100000) {
    epv.push_back({ em[i], i });
    opv.push_back({ om[i], i });
  }

  sort(epv.begin(), epv.end(), greater<pair<ll, ll>>());
  sort(opv.begin(), opv.end(), greater<pair<ll, ll>>());

  /*
    cout << "1111" << endl;
    cout << epv[0].first << endl;
    cout << epv[0].second << endl;
    cout << epv[1].first << endl;
    cout << epv[1].second << endl;

    cout << "2222" << endl;
    cout << opv[0].first << endl;
    cout << opv[0].second << endl;
    cout << opv[1].first << endl;
    cout << opv[1].second << endl;
    */

  if(epv[0].second == opv[0].second) {
    cout << n - max((epv[0].first + opv[1].first), (epv[1].first + opv[0].first)) << endl;
  } else {
    cout << n - (epv[0].first+opv[0].first) << endl;
  }

}


Measured memory_bytes: 17504
s = input()
k = int(input())

l_s = len(s)
U = set()
for c in [chr(i) for i in range(97, 97+26)]:
    for i in range(l_s):
        if c == s[i]:
            for j in range(k):
                U.add(s[i:i + j + 1])
    if len(U) > 5:
        break
print(sorted(list(U))[k - 1])

Measured memory_bytes: 3060
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) x.begin(),x.end()
const long double PI = acos(-1.0L);
const long long MOD = 1000000007LL;
//const long long MOD = 998244353LL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
template<class T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true;} return false; }
template<class T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true;} return false; }
///////////////////////////////////////////////////////////////////////////////////////////////////

vector<vector<int>> G;
bool check[100000];
vector<int> ans;

void dfs(int v) {
    check[v] = true;
    ans.emplace_back(v);
    for (auto nv : G[v]) {
        if (check[nv]) continue;
        dfs(nv);
        break;
    }
    return;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int N,M; cin >> N >> M;
    G.resize(N);
    rep(i,M) {
        int a,b; cin >> a >> b;
        a--; b--;
        G[a].emplace_back(b);
        G[b].emplace_back(a);
    }

    dfs(0);
    reverse(all(ans));
    dfs(0);

    ans.erase(unique(all(ans)),ans.end());

    cout << ans.size() << endl;
    for (auto i : ans) cout << i+1 << " ";
    cout << endl;
}

Measured memory_bytes: 7928
#include <algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<string>
#include <sstream>

#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<limits.h>
#define MOD 1000000007
using lll = long long;
using ull = unsigned long long;
using namespace std;



int main(){
  lll ii,jj,kk,max,sum=0;
  char* buffer;
  string fmt = "%06lld";
  string fmt1,fmt2,fmt3;
  char fmtc[10000];
  string s;
  ostringstream ss;
  lll mod;
  cin >> s;
  int N = 13;

  long dp[N];
  long mul = 1;
  long nextDP[N];  
  long c = s[0] - '0'; 
  //cout << "c:"  << c << endl;
  memset(dp,0,N*sizeof(long));
  dp [0] = 1;

  //文字列の長さ
  memcpy(nextDP,dp,N*sizeof(long));
  //cout << nextDP[0] << endl;
  for(int ii=s.length()-1; ii>=0; ii--){
    char c = s[ii];
    memset(nextDP,0,N*sizeof(long));
    //次の状態
    // ? の場合
    if(c == '?'){
      for(int kk=0;kk<10;kk++){
        for(jj=0;jj<N;jj++){
          nextDP[(kk * mul + jj) % N] += dp[jj];
          nextDP[(kk * mul + jj) % N] %= MOD;
        }
      }
    }
    //？以外の場合
    else{
      int kk = (int)(s[ii] - '0');

      for(int jj = 0; jj< N ; jj++){

        nextDP[(kk * mul + jj) % N] += dp[jj];
        nextDP[(kk * mul + jj) % N] %= MOD;

      }
    }

    mul *= 10;
    mul %= N;

    memcpy(dp,nextDP,sizeof(long)*N);

    
  }
  cout << dp[5] << endl;
  return 0;
}


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

#ifdef _DEBUG
#define debug(x) cerr << "line: " << __LINE__ << ", func: " << __func__ << " ->  " << #x << " = " << x << endl
#else
#define debug(x)
#endif

#define all(s) begin(s), end(s)
#define rall(s) rbegin(s), rend(s)
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define rrep(i, a, b) for (int i = ((a)-1); i >= (b); i--)
#define pb push_back
#define sz(a) int((a).size())

using namespace std;

using ll = long long;
using ull = unsigned long long;
using i_i = pair<int, int>;
using ll_ll = pair<ll, ll>;
using d_ll = pair<double, ll>;
using ll_d = pair<ll, double>;
using d_d = pair<double, double>;

static constexpr ll LL_INF = 1LL << 60;
static constexpr int I_INF = 1 << 28;
static constexpr double PI = static_cast<double>(3.14159265358979323846264338327950288);
static constexpr double EPS = numeric_limits<double>::epsilon();

static map<type_index, const char* const> scanType = {
    {typeid(int), "%d"}, {typeid(ll), "%lld"}, {typeid(double), "%lf"}, {typeid(char), "%c"}};

template <class T> static void scan(vector<T>& v);
[[maybe_unused]] static void scan(vector<string>& v, bool isWord = true);
template <class T> static inline bool chmax(T& a, T b);
template <class T> static inline bool chmin(T& a, T b);
template <class A, size_t N, class T> static void Fill(A (&arr)[N], const T& val);

int main(int argc, char* argv[]) {
  long long N;
  scanf("%lld", &N);
  std::vector<std::string> s(N);
  map<string, ll> m;
  for (int i = 0; i < N; i++) {
    std::cin >> s[i];
    sort(all(s[i]));
    m[s[i]]++;
  }

  ll ans = 0;
  for (string v : s) {
    m[v]--;
    ans += m[v];
  }
  cout << ans << endl;
  return 0;
}

template <class T> static void scan(vector<T>& v) {
  auto tFormat = scanType[typeid(T)];
  for (T& n : v) {
    scanf(tFormat, &n);
  }
}

static void scan(vector<string>& v, bool isWord) {
  if (isWord) {
    for (auto& n : v) {
      cin >> n;
    }
    return;
  }

  int i = 0, size = v.size();
  string s;
  getline(cin, s);

  if (s.size() != 0) {
    i++;
    v[0] = s;
  }

  for (; i < size; ++i) {
    getline(cin, v[i]);
  }
}

template <class T> inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}

template <class T> inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}

template <class A, size_t N, class T> void Fill(A (&arr)[N], const T& val) {
  std::fill((T*)arr, (T*)(arr + N), val);
}


Measured memory_bytes: 18176
#include <bits/stdc++.h>
using namespace std;
#define ll long long                                    // long long省略
#define pb push_back                                    // push_back省略
#define mp make_pair                                    // make_pair省略
#define fi first                                        // first省略
#define se second                                       // second省略
#define itn int                                         // int誤字保険
#define count cout                                      // cout誤字保険
#define vecotr vector                                   // vector誤字保険
#define opt() cin.tie(0); ios::sync_with_stdio(false)   // 入出力速度改善

#define rep(i,l,r)for(ll i=(l);i<(r);i++)               // 範囲[l, r)で刻み1のfor文(順方向)
#define repp(i,l,r,k)for(ll i=(l);i<(r);i+=(k))         // 範囲[l, r)で刻みkのfor文(順方向)
#define rrep(i,l,r)for(ll i=(r-1);i>=(l);i--)           // 範囲[l, r)で刻み1のfor文(逆方向)
#define rrepp(i,l,r,k)for(ll i=(r-1);i>=(l);i-=(k))     // 範囲[l, r)で刻みkのfor文(逆方向)
#define all(x) (x).begin(), (x).end()                   // vectorのポインタ位置指定用
#define max(p,q)((p)>(q)?(p):(q))                       // max拡張
#define min(p,q)((p)<(q)?(p):(q))                       // min拡張
#define bit(n,m)(((n)>>(m))&1)                          // 変数nのm番目のbitを取り出す

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

int dy[]={0, 0, 1, -1};                                 // 4方向近傍
int dx[]={1, -1, 0, 0};                                 // 4方向近傍


/*
   upll : (a<b)なら-1, (a=b)なら0, (a>b)なら1
 downll : (a<b)なら1, (a=b)なら0, (a>b)なら-1

 const void* a : 型を縛らずにconstをつける(=変数aが読み込み専用の変数であることを明示する)
        (ll*)a : 変数aがconst long long *型であると明示する
*/
// int upll(const void*a, const void*b){return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;}
// int downll(const void*a, const void*b){return*(ll*)a<*(ll*)b?1:*(ll*)a>*(ll*)b?-1:0;}
// void sortup(ll*a,int n){qsort(a,n,sizeof(ll),upll);}
// void sortdown(ll*a,int n){qsort(a,n,sizeof(ll),downll);}
ll pom(ll a,ll n,int m){ll x=1;for(a%=m;n;n/=2)n&1?x=x*a%m:0,a=a*a%m;return x;}

#define INF ((1LL<<62)-(1LL<<31))
//#define MOD 998244353
#define MOD 1000000007
#define invp(a,p) pom(a,p-2,p)

int main(){
    const double PI=(acos(-1));
    double a, b, x;
    cin >> a >> b >> x;
    if(a*a*b/2.0 <= x){
        double ans = (180.0000000000/PI) * (atan(2*((a*a*b - x)/(a*a*a))));
        cout << fixed << setprecision(10) << ans << endl;
    }else{
        double ans = (180.0000000000/PI) * (PI/2 - atan(2*x/(a*b*b)));
        cout << fixed << setprecision(10) << ans << endl;
    }
    
}

Measured memory_bytes: 256
#ifndef LOCAL
#pragma GCC optimize ("O3")
#endif
#include <bits/stdc++.h>
using namespace std;
#define sim template < class c
#define ris return * this
#define mor > muu & operator << (
#define R22(r) sim > typename \
  enable_if<1 r sizeof dud<c>(0), muu&>::type operator<<(c g) {
sim > struct rge { c b, e; };
sim > rge<c> range(c h, c n) { return {h, n}; }
sim > auto dud(c* r) -> decltype(cerr << *r);
sim > char dud(...);
struct muu {
#ifdef LOCAL
stringstream a;
~muu() { cerr << a.str() << endl; }
R22(<) a << boolalpha << g; ris; }
R22(==) ris << range(begin(g), end(g)); }
sim, class b mor pair < b, c > r) { ris << "(" << r.first << ", " << r.second << ")"; }
sim mor rge<c> u) {
  a << "[";
  for (c i = u.b; i != u.e; ++i)
    *this << ", " + 2 * (i == u.b) << *i;
  ris << "]";
}
#else
sim mor const c&) { ris; }
#endif
muu & operator()() { ris; }
};
#define imie(r...) "[" #r ": " << (r) << "] "
#define imask(r...) "[" #r ": " << bitset<8 * sizeof(r)>(r) << "] "
#define arr(a, i) "[" #a imie(i) ": " << a[i] << "] "
#define arr2(a, i, j) "[" #a imie(i) imie(j) ": " << a[i][j] << "] "
#define debug (muu() << __FUNCTION__ << "#" << __LINE__ << ": ")

const int N = 1e5 + 7;
int a[N];
int b[N];
int c[N];
int n;

int dp[N][3];
const int inf = 1e9 + 7;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d %d %d", a + i, b + i, c + i);
    
    for (int i = 1; i <= n; ++i) {
        dp[i][0] = a[i] + max(dp[i - 1][1], dp[i - 1][2]);
        dp[i][1] = b[i] + max(dp[i - 1][0], dp[i - 1][2]);
        dp[i][2] = c[i] + max(dp[i - 1][0], dp[i - 1][1]);
    }
    
    printf("%d\n", max(dp[n][0], max(dp[n][1], dp[n][2])));
    return 0;
}


Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N;cin>>N;
  vector<int64_t>A(N);
  vector<int64_t>B(N);
  for(int i=0;i<N;i++)
    cin>>A.at(i);
  for(int i=0;i<N;i++)
    cin>>B.at(i);
  vector<pair<int64_t,int64_t>>C(N);
  for(int i=0;i<N;i++){
  pair<int64_t,int64_t>p(B[i],A[i]);
    C[i]=p;
  }sort(C.begin(),C.end());
  for(int i=0;i<N;i++)
    A.at(i)=C.at(i).second;
  for(int i=0;i<N;i++)
    B.at(i)=C.at(i).first;
  vector<int64_t>D(N);
  for(int i=0;i<N;i++){
  auto itr=lower_bound(B.begin(),B.end(),A[i]);
    int64_t k=distance(B.begin(),itr);
    D[i]=k;
  }vector<int64_t>E(N);for(int i=0;i<N;i++)E[i]=D[i];
  sort(E.begin(),E.end());
  bool x=true;
  for(int i=0;i<N;i++)
    if(i<E[i]){x=false;break;}
  if(!x)
    cout<<"No"<<endl;
  else{
  bool y=true;
    for(int i=0;i<N;i++)
      if(i!=E[i]){y=false;break;}
    if(!y)
      cout<<"Yes"<<endl;
    else{
    set<int64_t>S;S.insert(0);
      int64_t a=0;
      for(int i=0;i<N;i++){
      a=D[a];if(!S.count(a))S.insert(a);
        else{break;}
       }int n=S.size();
      if(n==N)
        cout<<"No"<<endl;
      else
        cout<<"Yes"<<endl;
    
    }
  
  }
  
  
 return 0;
}

Measured memory_bytes: 12496
n, m = list(map(int, input().split()))
dp = [pow(10, 10) for _ in range(pow(2, n))]

dp[0] = 0
for _ in range(m):
    a, b = list(map(int, input().split()))
    cs = list(map(int, input().split()))
    d = 0
    for c in cs:
        d += pow(2, (c-1))
    for i in range(pow(2, n)):
        dp[i|d] = min(dp[i|d], dp[i] + a)

if dp[pow(2,n)-1] == pow(10, 10):
    print(-1)
else:
    print(dp[pow(2,n)-1])


Measured memory_bytes: 47576
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
using namespace std;
typedef long long ll;
int INF = (1LL << 30) - 1;
int MOD = 1e9+7;
main(){
    int N,A,B,C,X;
    cin >> N >> A >> B >> C >> X;
    while(N){
        int cnt = 0;
        rep(i,0,N){
            int y;
            cin >> y;
            while(X != y && cnt <= 10000){
                X = (A * X + B) % C;
                cnt++;
            }
            X = (A * X + B) % C;
            cnt++;  
        }
        cnt--;
        if(cnt <= 10000)cout << cnt << endl;
        else            cout << -1 << endl;
        cin >> N >> A >> B >> C >> X;
    }
}


Measured memory_bytes: 2980
#include <iostream>
#include <queue>
using namespace std;
int main() {
  priority_queue<int> q;
  int c;
  for (int i = 0; i < 10; ++i) {
    cin >> c;
    q.push(c);
  }
  for (int i = 0; i < 3; ++i) {
    cout << q.top() << endl;
    q.pop();
  }
  return 0;
}

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

int main(){
  int H, W;
  while(1){
    cin >> H >> W;
    if(H == 0 && W == 0) break;
    for(int i = 1; i <= H; i++){
      for(int j = 1; j <= W; j++){
        if((i+j) % 2 == 0){
          cout << "#";
        }else{
          cout << ".";
        }
      }
      cout << endl;
    }
    cout << endl;
  }

  return 0;
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
#define assign(x,val) memset(x,val,sizeof(x))
#define all(x) (x).begin(), (x).end()
#define for0(i,n) for(ll i=0;i<n;++i)
#define for1(i,n) for(ll i=1;i<=n;++i)
#define ford(i,n) for(ll i=n;i>=1;--i)
#define forg(i,a,b) for(ll i=a;i<b;++i)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpi;
typedef pair<ll, ll> pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pll> vpl;
long long mod = 1000000007;
const long double PI = (long double)(3.1415926535897932384626433832795);


void solve(){
  int n;cin>>n;
  string s,t;cin>>s>>t;
  for0(i,n) cout<<s[i]<<t[i];
}

int main(){
	ll t = 1;
	//cin>>t;
	for0(i, t){
		solve();
	}
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#define int long long
using namespace std;

signed main() {
	int a,b,k;
  	cin >>a>>b>>k;
  	if(k>=a+b) cout << 0 << " " << 0 << "\n";
  	else {
    	if(k > a) cout << 0 << " " << (a+b)-k << "\n";
      	else cout << a-k << " " << b << "\n";
    }
  return 0;
}


Measured memory_bytes: 256
L, R = map(int, input().split())
if R - L >= 2019:
    print(0)
else:
    d = L - L % 2019
    L = L - d
    R = R - d
    ans = 2018
    for l in range(R - L):
        for r in range(R - L - l):
            s = ((L + l) * (L + l + r + 1)) % 2019
            if ans > s:
                ans = s
    print(ans)


Measured memory_bytes: 3060
from collections import deque

n = int(input())
a = list(map(int, input().split()))
b = deque([])

for i, ai in enumerate(a):
    if i % 2 == 0:
        b.append(ai)
    elif i % 2 == 1:
        b.appendleft(ai)
b = list(b)
print(*(b if n % 2 == 0 else b[::-1]))


Measured memory_bytes: 106384
#include <bits/stdc++.h>
#define rep(i, s, n) for (int i = (s); i < (int)(n); i++)
#define per(i, n, s) for (int i = (n-1); i >= (int)(s); i--)
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<x<<endl
using namespace std;
using ll = long long;
const ll MOD = 1e9+7;
const ll LINF = LLONG_MAX;
const int INF = INT_MAX;
const double PI=acos(-1);
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; }

int main(){
	ll n; cin>>n;
	ll ans=1;
	vector<ll> a(n);
	rep(i,0,n){
		cin>>a[i];
		if(a[i]==0){
			cout<<0<<endl;
			return 0;
		}
	}
	rep(i,0,n){
		if(a[i]>(ll)1e18/ans){
			cout<<-1<<endl;
			return 0;
		}
        ans*=a[i];
	}
	cout<<ans<<endl;
}

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

ll knapsack(ll n, ll W, ll w[], ll v[]){
  ll dp[n+1][W+1];
  for(ll i=0; i<n+1; i++){
  	for(ll j=0; j<W+1; j++){
      if(j == 0 || i==0){
        dp[i][j] =0;
      }
      else if(w[i-1] <= j){
        dp[i][j] = max(dp[i-1][j], v[i-1]+dp[i-1][j-w[i-1]]);
      }
      else{
        dp[i][j] = dp[i-1][j];
      }
    
    }
  }
  return dp[n][W];

}

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ll n,W;
  cin>>n>>W;
  ll w[n], v[n];
  for(ll i=0; i<n; i++){
    cin>>w[i]>>v[i];
  }
  ll ans = knapsack(n, W, w, v);
  cout<<ans<<"\n";   
  return 0;
}


Measured memory_bytes: 82476
#include<bits/stdc++.h>
using namespace std;
#define loop(I, N) for(int I = 1; I <= N; I++)
#define pool(I, N) for(int I = N; I >= 1; I--)
#define rep(I, N) for(int I = 0; I < N; I++)
#define per(I, N) for(int I = N - 1; I >= 0; I--)
#define FOR(I, L, R) for(int I = L; I <= R; I++)
#define FOD(I, R, L) for(int I = R; I >= L; I--)
#define SET(P, VAL) memset(P, VAL, sizeof(P));

int n, y, bi[3] = {10, 5, 1};
int main() {
	scanf("%d%d", &n, &y);
	y /= 1000;
	FOR(i, 0, n) FOR(j, 0, n - i) {
		if(10 * i + 5 * j + n - i - j == y) {
			printf("%d %d %d\n", i, j, n - i - j);
			return 0;
		}
	}
	printf("-1 -1 -1\n");
}


Measured memory_bytes: 256
n,k = map(int, input().split())
r,s,p = map(int, input().split())
t = str(input())
num = p*t.count('r') + r*t.count('s') + s*t.count('p')
w = ""
for i in range(n):
    if t[i] == "r":
        x = "p"
        y = p
    elif t[i] == "s":
        x = "r"
        y = r
    else:
        x = "s"
        y = s
    if i < k:
        w += x
    else:
        if w[i-k] == x:
            num -= y
            w += "q"
        else:
            w += x
print(num)

Measured memory_bytes: 9332
#include <iostream>
#include <algorithm>
using namespace std;
static const int MAX = 1000000;


int main(){
    int R[MAX], n;

    cin >> n;
    for(int i = 0; i < n; i++) cin >> R[i];

    int maxv = -2000000000; //十分小さい値を初期値に
    int minv = R[0];

    for(int i = 1; i < n; i++){  // ここで毎回R[i]を読み込めば，配列は不要
        maxv = max(maxv, R[i] - minv);  // 最大値を更新
        minv = min(minv, R[i]);  // ここまでの最小値を保持しておく
    }
    cout << maxv << endl;

    return 0;
}


Measured memory_bytes: 3924
n, k = map(int, input().split())
b = list(map(int, input().split()))
a = [0]
a.extend(b)
#print(a)
count = 1
idou = [0]*(n+1)
idousaki = a[1]
while idou[idousaki] == 0:
  idou[idousaki] = count
  idousaki = a[idousaki]
  count += 1

if k >= idou[idousaki]:
  amari = (k - idou[idousaki]) % (count -idou[idousaki])
  print(idou.index((idou[idousaki]+amari)))
else:
  print(idou.index(k))


Measured memory_bytes: 92876
from collections import defaultdict
from math import gcd
import time
import sys
from collections import Counter
import itertools
import math
# read = sys.stdin.buffer.read
# readline = sys.stdin.buffer.readline
# readlines = sys.stdin.buffer.readlines
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split(" ")))
ans = 1
lim = 10**18

if 0 in A:
    print("0")
    exit()


for i in range(N):
    ans *= A[i]
    if ans > lim:
        print("-1")
        exit()

print(ans)


Measured memory_bytes: 23120
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define pb push_back
#define all(v) v.begin(), v.end()
#define bigger (char)toupper
#define smaller (char)tolower
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;
typedef unsigned long long ull;

int main() {
    int N;
    cin>>N;
    vi H(N);
    rep(i,N) {
        cin>>H[i];
    }
    int answer=0;
    rep(i,N) {
        bool counter=true;
        for(int j=0; j<i; j++) {
            if(H[i]<H[j]) {
                counter=false;
            }
        }
        if(counter) answer++;
    }
    cout<<answer<<endl;
}

Measured memory_bytes: 256
import numpy as np


def main():
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]
    A = np.zeros([H + 2, W + 2], bool)

    for h in range(H):
        for w in range(W):
            if S[h][w] == "#":
                A[h + 1, w + 1] = True

    B = np.zeros([H, W], np.int32)
    for h in range(H):
        for w in range(W):
            B[h, w] = np.count_nonzero(A[h:h + 3, w:w + 3])

    B = B.tolist()
    for h in range(H):
        for w in range(W):
            if S[h][w] == "#":
                B[h][w] = "#"

    for h in range(H):
        b = list(map(str, B[h]))
        print("".join(b))


main()


Measured memory_bytes: 12460
import numpy as np
num = int(input())
ary = [[0, 0, 0]]
for _ in range(num):
    ary += [list(input().split())]
ary = np.array(ary, dtype=int)

dt = ary[1:, 0] - ary[:-1, 0]
dx = ary[1:, 1:] - ary[:-1, 1:]
dx = np.abs(dx).sum(axis=1)

if np.all(dt >= dx) and np.all((dt - dx) % 2 == 0):
    print("Yes")
else:
    print("No")

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


int main(){
    string S_prime, T;
    cin >> S_prime;
    cin >> T;
    for(int i = S_prime.length() - T.length(); i >= 0; i--){
        string S(S_prime);
        bool ok = true;
        for(int j = 0; j < T.length(); j++){
            if(S[i+j] == T[j] || S[i+j] == '?'){
                S[i+j] = T[j];
            }else{
                ok = false;
            }
        }
        if(!ok){
            continue;
        }else{
            for(int j = 0; j < S.length(); j++){
                if(S[j] == '?'){
                    S[j] = 'a';
                }
            }
            cout << S << endl;
            return 0;
        }
    }
    cout << "UNRESTORABLE" << endl;
}


Measured memory_bytes: 256
# Reference: https://mathtrain.jp/kyorenketsu#:~:text=%E5%BC%B7%E9%80%A3%E7%B5%90%E6%88%90%E5%88%86%E5%88%86%E8%A7%A3%E3%81%A8,%E9%80%A3%E7%B5%90%E6%88%90%E5%88%86%EF%BC%89%E3%81%AB%E5%B1%9E%E3%81%97%E3%81%BE%E3%81%99%E3%80%82
# Reference: https://tjkendev.github.io/procon-library/python/graph/scc.html
# Strongly Connected Components
# This is made for "AtCoderLibraryPracticeContest/G-SCC"
from sys import stdin, setrecursionlimit
setrecursionlimit(10**9)
input = stdin.buffer.readline

# n = the number of nodes
# m = the number of edges
n, m = map(int, input().split())

edges = [[] for _ in range(n)]
reversed_edges = [[] for _ in range(n)]
for _ in range(m):
    i, j = map(int, input().split())
    edges[i].append(j)
    reversed_edges[j].append(i)

def scc(n, edges, reversed_edges):
    order = []
    seen = [True] * n

    def dfs(node):
        seen[node] = False
        for i in edges[node]:
            if seen[i]:
                dfs(i)
        order.append(node)

    for i in range(n):
        if seen[i]:
            dfs(i)

    groups = []
    seen = [True] * n
    for start in reversed(order):
        if seen[start]:
            ### DFS
            seen[start] = False
            todo = [start]
            group = [start]
            while len(todo) > 0:
                node = todo.pop(-1)
                for j in reversed_edges[node]:
                    if seen[j]:
                        seen[j] = False
                        todo.append(j)
                        group.append(j)
            ###
            group.reverse()
            groups.append(group)

    return groups

groups = scc(n, edges, reversed_edges)
print(len(groups))
for group in groups:
    print(len(group), ' '.join(map(str, group)))

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)

int main()
{
    int n, m, x;
    cin >> n >> m >> x;
    vector<int> c(n, 0);
    vector<vector<int>> a(n, vector<int>(m, 0));
    rep(i, n)
    {
        cin >> c[i];
        rep(j, m)
        {
            cin >> a[i][j];
        }
    }
    vector<int> cc((1 << n), 0);
    vector<vector<int>> aa((1 << n), vector<int>(m, 0));

    const int ans_max = 30000000;
    int ans = ans_max;
    rep(i, (1 << n))
    {
        // cerr << i << endl;
        rep(j, n)
        {
            if (i & (1 << j))
            {
                cc[i] += c[j];
                rep(k, m)
                {
                    aa[i][k] += a[j][k];
                }
            }
        }
        bool is_rikai = true;
        rep(j, m)
        {
            // cerr << aa[i][j] << " ";
            if (aa[i][j] < x)
            {
                is_rikai = false;
            }
        }
        // cerr << "  --   " << cc[i];
        // cerr << endl;
        if (is_rikai)
        {
            ans = min(ans, cc[i]);
        }
    }

    if (ans == ans_max)
    {
        cout << -1 << endl;
    }
    else
    {
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 4000
#include <stdio.h>
#include <algorithm>
using namespace std;
main()
{
    int num;
    scanf("%d",&num);
    int animal[num];
    for (int i=0;i<num;i++)
    {
        scanf("%d",&animal[i]);
    }
    sort(animal,animal+num);
    long long sum=animal[0];
    long long cnt=1;
    for (int i=1;i<num;i++)
    {
        if (sum*2>=animal[i])
        {
            cnt++;
        }
        else
        {
            cnt=1;
        }
        sum+=animal[i];
    }
    printf("%d",cnt);
}


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

int main(){

  int n, s[12], num[12][2], valid, len, cnt;
  
  while(cin >> n){
    if(n == 0) break;
    for(int i=0; i<n; i++){
      cin >> s[i];
    }  
    
    cnt = 0;

    do{
      valid = 0;
      num[0][0] = 0;
      len = 1;
      num[0][0] = s[0];
      num[0][1] = 1;
      
      for(int i=1; i<n; i++){
        for(int j=0; j<len; j++){
          if(num[j][0] == s[i]){
            num[j][1]++;
            break;
          }
          else if(j == len - 1){
            num[len][0] = s[i];
            num[len][1] = 1;
            len++;
            break;
          }
        }
      }    

      for(int i=0; i<n; i++){
        for(int j=0; j<len; j++){
          if(num[j][0] == s[i] && num[j][1] != s[i]){
            s[i] = num[j][1];
            valid = 1;
            break;
          }
        }
      }

      if(valid == 1) cnt++;
    }while(valid == 1);
    
    cout << cnt << endl;
    for(int i=0; i<n; i++){
      cout << s[i];
      if(i != n-1) cout << " ";
      else cout << endl;
    }
  }

  return 0;

}

Measured memory_bytes: 1160
// https://atcoder.jp/contests/dp/tasks/dp_e

#include "algorithm"
#include "iostream"
#include "set"
#include "vector"
#define rep(i, from, to) for (ll i = from; i < (to); ++i)
using namespace std;
typedef long long ll;
template <typename T>
using V = vector<T>;
template <typename T>
inline bool chmax(T& a, T b);
template <typename T>
inline bool chmin(T& a, T b);
void print_ints(vector<ll> v);
template <typename T>
void drop(T a);

void solve() {
  ll N, W;
  cin >> N >> W;

  ll v_sum = 0;

  V<pair<ll, ll>> items(N);
  rep(i, 0, N) {
    cin >> items[i].first;
    cin >> items[i].second;
    v_sum += items[i].second;
  }

  ll INF = 1e18;
  // dp[i][j]: i 番目のアイテムまでで価値を j 以上にするために必要な最小の重さ
  V<V<ll>> dp(N + 1, V<ll>(v_sum + 1, INF));
  rep(i, 0, N + 1) dp[i][0] = 0;

  rep(i, 1, N + 1) {
    auto item = items[i - 1];
    auto w = item.first;
    auto v = item.second;

    rep(j, 0, v_sum + 1) {
      chmin(dp[i][j], dp[i - 1][j]);

      if (j - v >= 0) {
        chmin(dp[i][j], dp[i - 1][j - v] + w);
      }
    }
  }

  ll res = 0;
  rep(v, 0, v_sum + 1) {
    if (dp[N][v] <= W) chmax(res, v);
  }

  cout << res << endl;
}

struct exit_exception : public std::exception {
  const char* what() const throw() { return "Exited"; }
};

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

  try {
    solve();
  } catch (exit_exception& e) {
  }

  return 0;
}
#endif

template <typename T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}

template <typename T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}

void print_ints(vector<ll> v) {
  rep(i, 0, v.size()) {
    if (i > 0) {
      cout << " ";
    }

    cout << v[i];
  }

  cout << endl;
}

template <typename T>
void drop(T res) {
  cout << res << endl;
  throw exit_exception();
}


Measured memory_bytes: 80256
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int main() {
  string c;
  cin >> c;
  if (c=="a"||c=="i"||c=="u"||c=="e"||c=="o") {
    cout << "vowel" << endl;
  }
  else {
    cout << "consonant" << endl;
  }
}


Measured memory_bytes: 3592
def slove():
    import sys
    input = sys.stdin.readline
    x = int(input().rstrip('\n'))
    t = 0
    cnt = 0
    for i in range(1, 10 ** 10):
        cnt += 1
        t += i
        if t >= x:
            print(cnt)
            exit()


if __name__ == '__main__':
    slove()


Measured memory_bytes: 38384
package main

import "fmt"

func main() {
	var N int
	fmt.Scan(&N)
	P, Q := make([]int, N), make([]int, N)
	for i := 0; i < N; i++ {
		fmt.Scan(&P[i])
	}
	for i := 0; i < N; i++ {
		fmt.Scan(&Q[i])
	}
	arr := make([]int, N)
	for i := 1; i <= N; i++ {
		arr[i-1] = i
	}
	np := next_permutation(arr)
	a, b := 0, 0
	i := 1
	for {
		lis := np()
		if len(lis) == 0 {
			break
		}
		if a == 0 {
			flagP := true
			for j := 0; j < N; j++ {
				if lis[j] != P[j] {
					flagP = false
				}
			}
			if flagP {
				a = i
			}
		}
		if b == 0 {
			flagQ := true
			for j := 0; j < N; j++ {
				if lis[j] != Q[j] {
					flagQ = false
				}
			}
			if flagQ {
				b = i
			}
		}
		i++
	}
	fmt.Println(abs(a - b))
}

func abs(x int) int {
	if x < 0 {
		x *= -1
	}
	return x
}

func next_permutation(arr []int) func() []int {
	ret := append([]int{}, arr...)
	_next_permutation := func() []int {
		n := len(ret)
		for i := n - 2; i >= 0; i-- {
			if ret[i] < ret[i+1] {
				j := n
				for {
					j -= 1
					if ret[i] < ret[j] {
						break
					}
				}
				ret[i], ret[j] = ret[j], ret[i]
				for k := n - 1; i < k; i, k = i+1, k-1 {
					ret[i+1], ret[k] = ret[k], ret[i+1]
				}
				return ret
			}
		}
		return []int{}
	}
	return _next_permutation
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#include <boost/range/adaptor/reversed.hpp>
#include <boost/range/algorithm/sort.hpp>
#include <boost/range/irange.hpp>

using namespace std;
using boost::irange;
using boost::sort;
using boost::adaptors::reversed;

int main() {
    int n, x, y;
    cin >> n >> x >> y;

    vector<vector<int>> dist(n + 1, vector<int>(n + 1));
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (i <= x) {
                if (j <= x + (y - x) / 2) {
                    dist[i][j] = j - i;
                } else if (j <= y) {
                    dist[i][j] = x - i + y - j + 1;
                } else {
                    dist[i][j] = dist[i][j - 1] + 1;
                }
            } else {
                if (j <= y) {
                    dist[i][j] = min(j - i, i - x + y - j + 1);
                } else {
                    dist[i][j] = dist[i][j - 1] + 1;
                }
            }
        }
    }


    vector<int> ans(n);
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
            ans[dist[i][j]] += 1;

    for (int k = 1; k < n; k++) cout << ans[k] << endl;
}


Measured memory_bytes: 16000
#include <iostream>
#include <sstream>
using namespace std;
#include <bits/stdc++.h>
#define  go return 0
#define pb push_back
#include<utility>
#include <algorithm>
#include<iterator>
typedef long long ll;
typedef double db;
#define lp1(i, n)  for(int i=0; i<(int)(n); ++i)
#define lp2(i, n)  for(int i=1; i<=(int)(n); ++i)
#define lp3(j, m)  for(int j=0; j<(int)(m); ++j)
#define all(v)   ((v).begin()), ((v).end())
#define sz(v)    ( (int)((v).size()) )
typedef vector<int> vi;
const int N=1e5+5;
int arr[N];
int main(){
 string s;
 int f=1;
 cin>>s;
// RUDLUDR
  for(int i=0 ; i<s.size() ; i++)
  {

          if(i%2==0 && s[i]=='L' )
            f=0;
          if(i%2!=0 && s[i]=='R')
            f=0;

  }
  if(f)
    cout<<"Yes";
  else
    cout<<"No";
go;
}


Measured memory_bytes: 256
using System;
class P{

    static void Main(){
        var s=Console.ReadLine();
        long c=0,cW=0;
        for(int i=0;i<s.Length;i++){
            if(s[i]=='W'){
                c+=i-cW;
                cW++;
            }
        }
        Console.WriteLine(c);
    }
}

Measured memory_bytes: 11616
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<unordered_map>
using ull = unsigned long long;
using ll = long long;
using namespace std;

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

    unordered_map<char, int> charmap;

    for (char c : s) {
        charmap[c]++;
    }

    for(char check = 'a'; check <= 'z'; check++) {
        if (charmap.count(check) == 0) {
            cout << check << endl;
            return 0;
        }
    }

    cout << "None" << endl;

    return 0;
}

Measured memory_bytes: 512
//#include <tourist>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> p;
const int INF = 1e9;
const ll LINF = ll(1e18);
const int MOD = 1000000007;
const int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
const int Dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, Dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
#define rep(i, n) for (int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()
#define debug(v)          \
    cout << #v << ":";    \
    for (auto x : v)      \
    {                     \
        cout << x << ' '; \
    }                     \
    cout << endl;
template <class T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}
//cout<<fixed<<setprecision(15);有効数字15桁
//-std=c++14
//-std=gnu++17
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    string ans="";
    rep(i,3){
        cin>>s;
        ans+=s[0];
    }
    cout<<ans<<"\n";
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
#define FOR(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define FORR(i, n) for(ll i = (ll)n - 1LL; i >= 0LL; i--)
#define rep(i, n) FOR(i, 0, n)
#define ALL(x) begin(x), end(x)
using namespace std;
using ll = long long;
constexpr ll Mod = 998244353;
constexpr ll mod = 1e9 + 7;
constexpr ll inf = 1LL << 60;
const double PI = acos(-1);
template <typename T1, typename T2> inline bool chmax(T1 &a, T2 b) {
    return a < b && (a = b, true);
}
template <typename T1, typename T2> inline bool chmin(T1 &a, T2 b) {
    return a > b && (a = b, true);
}
/*-------------------------------------------*/

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

    ll k;
    ll sum = 0;
    cin >> k;

    FOR(i, 1, k + 1) {
        ll x = k / i;
        ll y = x * (x + 1) / 2;
        sum += i * y;
    }

    cout << sum << endl;

    return 0;
}

Measured memory_bytes: 3664
#include "bits/stdc++.h"
using namespace std;

int main(){
	int n,w,h;
	cin>>n>>w>>h;
	vector<int> pw(w+1e6);
	vector<int> mw(w+1e6);
	vector<int> ph(h+1e6);
	vector<int> mh(h+1e6);
	
	for(int i=0;i<n;i++){
		int x,y,z;
		cin>>x>>y>>z;
		int mx=x-z;
		if(mx<0)mx=0;
		pw[mx]++;
		mw[x+z+1]--;
		
		int my=y-z;
		if(my<0)my=0;
		ph[my]++;
		mh[y+z+1]--;
	}
	
	int flag=1;
	
	int tmp=pw[0];
	
	for(int i=1;i<=w;i++){
		tmp+=mw[i];
		if(tmp==0){
			flag=0;
			break;
		}
		tmp+=pw[i];
	}
	
	if(flag==1){
		cout<<"Yes"<<endl;
		return 0;
	}
	
	
	
	flag=1;
	
	tmp=ph[0];
	
	for(int i=1;i<=h;i++){
		tmp+=mh[i];
		if(tmp==0){
			flag=0;
			break;
		}
		tmp+=ph[i];
	}
	
	if(flag==1){
		cout<<"Yes"<<endl;
		return 0;
	}
	
	cout<<"No"<<endl;
	return 0;
}

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

using namespace std;

typedef long long ll;

const ll LongINF=1e13+7;
const int INF=1e9+7;
const int dx[]={0,1,0,-1};
const int dy[]={1,0,-1,0};

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;}
template <class T, class Y>T GCD(T a, Y b){if(a<b){int c=a;a=b;b=c;}if (a % b == 0){return b;}return GCD(b, a % b);}
void clear(queue<pair<int, int>> &q){queue<pair<int, int>> empty;swap(q, empty);} //queueの中身の型は適時変更を忘れない

#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define rv reverse

int main(){
    int N,T;
    cin>>N>>T;
    vector<int> t(N,0);
    rep(i,N)cin>>t[i];
    ll ANS=T;//最後の人が押したのは重複しない

    rep(i,N-1){
        if(T>=t[i+1]-t[i])ANS+=(t[i+1]-t[i]);
        else ANS+=T;
    }
    cout<<ANS<<endl;

    return 0;
}

//a=97,z=122

Measured memory_bytes: 1024
# -*- coding: utf-8 -*-
# モジュールのインポート
import itertools

# 標準入力の取得
N,M,Q = list(map(int, input().split()))
a,b,c,d = [],[],[],[]
for q in range(Q):
    a_q,b_q,c_q,d_q = list(map(int, input().split()))
    a.append(a_q)
    b.append(b_q)
    c.append(c_q)
    d.append(d_q)

# 求解処理
l = list(range(1, M+1))
result = 0
for A in itertools.combinations_with_replacement(l, N):
    score = 0
    for a_i,b_i,c_i,d_i in zip(a, b, c, d):
        if A[b_i-1] - A[a_i-1] == c_i:
            score += d_i

    result = max(result, score)

# 結果出力
print(result)

Measured memory_bytes: 9220
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define MAX 105
int w[MAX],v[MAX],dp[100005];
int knapsack(int n,int x)
{
	for(int i=0;i<=n;i++)
	for(int j=x;j>=0;j--)
	{
		if(i==0||j==0)
		dp[j]=0;
		else if(j>=w[i])
		{
			if(dp[j]<dp[j-w[i]]+v[i])
			dp[j]=dp[j-w[i]]+v[i];
		}
	}
	int m=0;
	for(int i=0;i<=x;i++)
	if(dp[i]>m)
	m=dp[i];
	return m;
}
signed main()
{
	int n,x,i;
	cin>>n>>x;
	for(i=1;i<=n;i++)
	{
		cin>>w[i]>>v[i];
	}
	cout<<knapsack(n,x)<<"\n";
}

Measured memory_bytes: 1024
#include<cstdio>
#include<cmath>
int main()
{
	int n;
	while (~scanf("%d", &n))
	{
		int x = (floor(n / 1.08) + 1)*1.08;
		if (floor(floor(n / 1.08)*1.08) == n)
			printf("%.0f\n", floor(n / 1.08));
		else if (floor((floor(n / 1.08 )+1)*1.08) == n)
			printf("%.0f\n", floor(n / 1.08 + 1));
		else
			printf(":(\n");
	}
}

Measured memory_bytes: 128
N = int(input())
A, B = map(int, input().split())
P = map(int, input().split())

memo = [0]*3
for e in P:
    if e <= A:
        memo[0] += 1
    elif e <= B:
        memo[1] += 1
    else:
        memo[2] += 1
print(min(memo))



Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
// InSane Code	...	

int main(int argc , char** argv){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	Int n;
	cin >> n;
	vector<Int> v(n) , arr(n,0);
	vector<Int> idx[30];
	// arr[i] will contain count of all element before ith element such that
	// arr[i-cnt] .. arr[i] xor == sum. 
	for(Int &i:v){
		cin >> i;
	}
	Int res = 0;
	for(Int i = 0 ; i < n ; ++i){
		Int num = v[i];
		Int ite = 0;
		while(num){
			if(num & 1){
				idx[ite].push_back(i);
			}
			ite++;
			num /= 2;
		}
	}
	for(Int i = 0 ; i < n ; ++i){
		Int num = v[i] , J = 0 , I = 0 , flag = 0;
		Int Y = -1;
		Int cnt = 0;
		while(I < 22){
			if(num & 1){
				Int W = lower_bound(idx[I].begin() , idx[I].end() , i) - idx[I].begin();
				if(W > 0){
					J = max(J , idx[I][W-1]);
					flag = 1;
				}
			}	
			else{
				Int W = lower_bound(idx[I].begin() , idx[I].end() , i) - idx[I].begin();
				if(W > 1){
					Y = max(Y , idx[I][W-2]);		
				}
			}
			I++;
			num /= 2;
		}
		if(flag == 0){
			cnt = i + 1;
		}
		else{
			cnt = i - J;
		}
		if(Y != -1){
			cnt = min(cnt , i - Y);
		}
		res += cnt;
	}
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 19748
N,M,C = map(int,input().split())
b_list = list(map(int, input().split()))

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

cnt = 0
for code in codes:
#     print(code,b_list)
    result = C
    for a,b in zip(code, b_list):
        result += a*b
#         print(result)
    if result > 0:
        cnt += 1
        
print(cnt)

Measured memory_bytes: 38256
N,K = map(int,input().split())
S = input()
T = '0' + S + '0'

ans = 0
k = 0
for i,(a,b) in enumerate(zip(S,S[1:])):
    if a=='0' and b=='1':
        k += 1
    elif k==K and a=='1' and b=='0':
        ans = max(ans, i+1)
        break
else:
    print(N)
    exit()

k = 0
S = S[::-1]
for i,(a,b) in enumerate(zip(S,S[1:])):
    if a=='0' and b=='1':
        k += 1
    elif k==K and a=='1' and b=='0':
        ans = max(ans, i+1)
        break
else:
    print(N)
    exit()

x = []
y = []
for i,(a,b) in enumerate(zip(T,T[1:])):
    if a==b: continue
    if a=='0':
        x.append(i)
    else:
        y.append(i)

for a,b in zip(x,y[K:]):
    ans = max(ans, b-a)
print(ans)

Measured memory_bytes: 7684
#include <iostream>

using namespace std;

int main() {
    int N;
    cin >> N;
    
    int A[3]={0};
    for(int n=0; n<N; n++) {
        long long int a;
        cin >> a;
        if(a%4==0) {
            A[0]++;
        } else if(a%4==2) {
            A[2]++;
        } else {
            A[1]++;
        }
    }
    
    if(A[0]>=A[1]) {
        cout << "Yes" << endl;
    } else if(A[0]==A[1]-1 && A[2]==0) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
    
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
const int N = 100000+10;
typedef long long LL;
int n,m;char s[N],t[N];
int gcd(int x,int y){
    return y==0?x:gcd(y,x%y);
}
int main(){
    scanf("%d%d",&n,&m);
    scanf("%s%s",s+1,t+1);
    int g=gcd(n,m);
    bool ok=1;
    for(int i=1;i<=g;i++){
        if(s[(i-1)*(n/g)+1]!=t[(i-1)*(m/g)+1])ok=0;
    }
    if(ok)printf("%lld\n", 1LL*n*m/g);
    else printf("-1\n");
}

Measured memory_bytes: 384
#include <iostream>
using namespace std;
 
int main() {
  unsigned long long i, N, res = 1;
  cin >> N;
  
  for (i = 1; i <= N; ++i) {
    res = res*i % (10*10*10*10*10*10*10*10*10 + 7);
  }
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#define MAX 1000000

/* 正四面体数列 */
int tetra[200]; /* 10^6以下の正四面体数は180個 */
int tetra_l;
int tetra_odd[100];
int tetra_odd_l;

int divide[MAX+1]; /* ある正整数を和で表すために必要な正四面体数の個数 */
int divide_odd[MAX+1]; /* ある正整数を和で表すために必要な「奇数」正四面体数の個数 */
#define UNKNOWN 0

int main(void) {
	int n, i;

	// 正四面体数列を生成する
	for (i = 1, tetra_l = 0, tetra_odd_l = 0; (n = i * (i + 1) * (i + 2) / 6) <= MAX; i++) {
		tetra[tetra_l++] = n;
		if (n % 2 != 0) tetra_odd[tetra_odd_l++] = n; /* 奇数のみの正四面体数列 */
	}

	/* 初期化する */
	for (n = 0; n <= MAX; n++) {
		divide[n] = UNKNOWN;
		divide_odd[n] = UNKNOWN;
	}

	/* 入力されうる全ての正整数について、必要な正四面体数の個数を求める */
	/* 正四面体数 */
	for (i = 0; i < tetra_l; i++) divide[tetra[i]] = 1;
	for (i = 0; i < tetra_odd_l; i++) divide_odd[tetra_odd[i]] = 1;
	/* 正四面体数でない正整数 */
	for (n = 1; n <= MAX; n++) {
		/* (個数が既知の正整数 + 正四面体数) に必要な個数は、その既知の個数に1を加えた数である */
		for (i = 0; i < tetra_l && n + tetra[i] <= MAX; i++) {
			if (divide[n + tetra[i]] == UNKNOWN || divide[n] + 1 < divide[n + tetra[i]]) {
				divide[n + tetra[i]] = divide[n] + 1;
			}
		}
		/* 奇数のみの場合 */
		for (i = 0; i < tetra_odd_l && n + tetra_odd[i] <= MAX; i++) {
			if (divide_odd[n + tetra_odd[i]] == UNKNOWN || divide_odd[n] + 1 < divide_odd[n + tetra_odd[i]]) {
				divide_odd[n + tetra_odd[i]] = divide_odd[n] + 1;
			}
		}
	}

	/* 与えられる正整数毎の処理 */
	while (scanf("%d", &n) == 1 && n > 0 && n <= MAX) printf("%d %d\n", divide[n], divide_odd[n]);

	return 0;
}

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

int main(){
  
  int N; int M;
  cin >> N >> M;
  int total=0;
  int tmp;
  for(int i=0;i<M;i++){
    cin >> tmp;
    total += tmp;
  }
  
  if(total > N) cout << -1 << endl;
  else cout << N-total << endl;
  
}

Measured memory_bytes: 3620
x = int(input())


def f(a, b):
    return a**5-b**5


divisors = set()
for i in range(1, int(10**9**.5)+1):
    if x % i == 0:
        divisors |= {i, x//i}


for b in range(-1000, 1000):
    for div in divisors:
        a = div+b
        if f(a, b) == x:
            print(a, b)
            exit()

Measured memory_bytes: 9344
#include<iostream>
using namespace std;
class Road{
public:
	int num;
	bool con;
};

int main(){
	int a,b;
	while(cin>>a>>b&&a!=0){
		Road **map;
		map=new Road*[a+1];
		for(int i=0;i<=a;++i){
			map[i]=new Road[b+1];
		}
		for(int i=0;i<=a;++i){
			for(int k=0;k<=b;++k){
				map[i][k].con=false;
				map[i][k].num=0;
			}
		}
		int x,y;
		int time;
		cin>>time;
		for(int i=0;i<time;++i){
			cin>>x>>y;
			map[x][y].con=true;
		}
		map[1][0].num=1;
		for(int i=1;i<=a;++i){
			for(int k=1;k<=b;++k){
				if(map[i][k].con==true)map[i][k].num=0;
				else{
					map[i][k].num=map[i-1][k].num+map[i][k-1].num;
				}
			}
		}
		cout<<map[a][b].num<<endl;
	}
	return 0;
}

Measured memory_bytes: 3016
k = int(input())

if k % 2 == 0 or k % 5 == 0:
  print(-1)
else:
  ans = 7
  cnt = 1
  while 1:
    if ans % k == 0:
      break
    else:
      cnt += 1
      ans *= 10
      ans += 7
      ans %= k

  print(cnt)      


Measured memory_bytes: 9052
import Data.Char
import Data.List
import qualified Data.ByteString.Char8 as B
main=print.solve.unfoldr(B.readInt.B.dropWhile isSpace)=<<(B.getLine>>B.getLine)
solve=g=<<foldr f(0,0,0)
f a(i,j,k)
  |a<0=(i+1,j,k)
  |a>0=(i,j,k+1)
  |otherwise=(i,j+1,k)
g(i,j,k)as
  |even i || j>0=sum bs
  |otherwise=sum bs-minimum bs*2
  where bs=map abs as

Measured memory_bytes: 21280