akhauriyash/Code-Regression huggingface dataset:
// #pragma GCC target ("avx2")
// #pragma GCC optimization ("O3")
// #pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define FastRead ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long int
#define ll int
#define bits_count __builtin_popcountll
#define endl '\n'
#define double double
#define ld double
#define FOR(i,a,n) for (ll i=(a);i<=(n);++i)
#define RFOR(i,a,n) for (ll i=(n);i>=(a);--i)
#define FI(i,n) for (ll i=0; i<(n); ++i)
#define ZERO(a) memset((a),0,sizeof((a)))
#define MINUS(a) memset((a),-1,sizeof((a)))
#define f first
#define s second
#define pb push_back
#define mk make_pair
#define all(g) g.begin(),g.end()
#define sz(x) (ll)x.size()
int fastMax(int x, int y) { return (((y-x)>>(32-1))&(x^y))^y; }
int fastMin(int x, int y) { return (((y-x)>>(32-1))&(x^y))^x; }

// #include <ext/pb_ds/assoc_container.hpp> // Common file
// #include <ext/pb_ds/tree_policy.hpp>     // Including tree_order_statistics_node_updat
// using namespace __gnu_pbds;
// typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

void solve(){

    string s; cin>>s;
    deque<char> d;
    for(char c:s) d.push_back(c);

    bool rever = 0;

    int q; cin>>q;

    while(q--){
        int type; cin>>type;
        if(type == 1) rever = 1-rever;
        else {
            int f; cin>>f;
            char c; cin>>c;
            if(f == 1){
                if(rever == 1) d.push_back(c);
                else d.push_front(c);
            }else {
                if(rever == 0) d.push_back(c);
                else d.push_front(c);
            }
        }
    }

    if(rever == 0){
        while(d.size()){
            cout<<d.front(); d.pop_front();
        }
    }else {
        while(d.size()){
            cout<<d.back(); d.pop_back();
        }
    }
}

signed main(){

   FastRead;    


    int t = 1; 
    // cin>>t; 
    FOR(i,1,t){
        // cout<<"Case #"<<i<<": ";
        solve();
    }
}

Measured memory_bytes: 976
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define setbits(x) __builtin_popcount(x)
#define setbitsll(x) __builtin_popcountll(x)
#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define se second
#define fi first
#define pai acos(-1)
#define fn(i,x) for(i=0;i<x;i++)
#define fs(i,s,x) for(i=s;i<x;i++)
#define fr(i,x,s) for(i=x;i>=s;i--)
#define fit(itr,s) for(itr=s.begin();itr!=s.end();itr++)
#define W while
#define pp pair<ll,ll>
#define ppi pair<int,int>
#define vl vector<ll>
#define vll vector<pp >
#define vi vector<int>
#define vii vector<ppi>
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define debug(x) cerr<<#x<<" :: "<<x<<endl;
#define debug2(x,y) cerr<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<endl;
#define debug3(x,y,z) cerr<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\t"<<#z<<" :: "<<z<<endl;
#define debug4(x,y,z,w) cerr<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\t"<<#z<<" :: "<<z<<"\t"<<#w<<" :: "<<w<<endl;
#define boost  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
const ll MAX=1e16;
const ll MM=1e18;
const ll mod=998244353;
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};

ll gcd(ll p, ll q){
    while(q != 0) {
        ll r = p % q;
        p = q;
        q = r;
    }
    return p;
}

ll expo(ll x,ll n,ll M=mod)
{
    ll ans=1;
    while(n>0)
    {
        if(n&1){ans=(ans*x)%M;}
                x=(x*x)%M;
                n>>=1;
    }
    return ans;
}
const ll MaxSize = 3e5;
ll facts[MaxSize], invFacts[MaxSize];

void preproc() {
  facts[0] = 1;
  for (int i = 1; i < MaxSize; i++) {
    facts[i] = ((ll)facts[i - 1] * i) % mod;
  }
  invFacts[MaxSize - 1] = expo(facts[MaxSize - 1], mod - 2,mod);

  for (int i = MaxSize - 2; i >= 0; i--) {
    invFacts[i] = ((ll)invFacts[i + 1] * (i + 1)) % mod;
  }
}

ll combination(ll n, ll k) {
  if(n<k) return 0;
  ll res = facts[n];
  res = ((ll)res * invFacts[k]) % mod;
  return ((ll)res * invFacts[n - k]) % mod;
}

////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////


void solve()
{
    
    int n;
    cin >> n;
    int  sum = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j<= n; j++) {
            for(int k = 1; k<= n; k++) {
                
                sum += gcd(i, gcd(j, k));
            }
        }
    }
    cout << sum << endl;
} 
int main()
{
  boost;
  int m;
  //cin >> m;
  int t=1;
  //cin>>t;
  while(t--)
  {
      solve();
  }
}



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

signed main() {

    int x;
    cin >> x;

    int sum = 0;
    sum = x / 500;
    x -= sum * 500;
    int uresi =  sum * 1000;

    sum = x / 5;
    uresi += sum * 5;
    cout << uresi << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
//lli p = 1000000007;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    lli n;
    cin>>n;
    int k = 1000002;
    int count[k];
    bool prime[k];
    int arr[k];
    for (int i=0;i<k;i++)
    {
        count[i] = 0;
        prime[i] = true;
        arr[i] = 0;
    }

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

    //Sieve
    for (int i=2;i<k;i++)
    {
        if (prime[i])
        {
            for (int j=i; j<k; j = j + i)
            {
                prime[j] = false;
                count[i] = count[i] + arr[j];
            }
        }
    }

    bool p_c = true;
    bool s_c = true;
    for (int i=1;i<k;i++)
    {
        if (count[i]>1) p_c = false;
        if (count[i]==n) s_c = false;
    }

    if (p_c)
    {
        cout<<"pairwise coprime\n";
    }
    else if (s_c)
    {
        cout<<"setwise coprime\n";
    }
    else
    {
        cout<<"not coprime\n";
    }
}

Measured memory_bytes: 12444
using System;

namespace abc178_a
{
    class Program
    {
        static void Main(string[] args)
        {
            int x = int.Parse(Console.ReadLine());

            if (x == 0)
            {
                Console.WriteLine("1");
            }
            else
            {
                Console.WriteLine("0");
            }
        }
    }
}


Measured memory_bytes: 27520
a11,a12,a13=map(int,input().split())
a21,a22,a23=map(int,input().split())
a31,a32,a33=map(int,input().split())
A=[a11,a12,a13,a21,a22,a23,a31,a32,a33]
n=int(input())
b=[]
for i in range(n):
  b.append(int(input()))
for i in range(n):
  for j in range(9):
    if b[i]==A[j]:
      A[j]=0
if A[0]==A[1] and A[1]==A[2] or A[3]==A[4] and A[3]==A[5] or A[6]==A[7] and A[6]==A[8] or A[0]==A[3] and A[0]==A[6] or A[1]==A[4] and A[1]==A[7] or A[2]==A[5] and A[2]==A[8] or A[0]==A[4] and A[0]==A[8] or A[2]==A[4] and A[2]==A[6]:
  print("Yes")
else:
  print("No")

Measured memory_bytes: 3064
N, C = map(int, input().split())
max_size = 10 ** 5
record_list = [[int(i) - 1 for i in input().split()] for _ in range(N)]
ans_list = [0 for _ in range(max_size)]
for c in range(C):
    T = [0 for _ in range(max_size + 1)]
    for s, t, i in record_list:
        if i == c:
            T[s] += 1
            T[t + 1] -= 1
    for i in range(max_size):
        T[i + 1] += T[i]
    for i in range(max_size):
        ans_list[i] += T[i] > 0
print(max(ans_list))

Measured memory_bytes: 179268
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <algorithm>
#include <sstream>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <numeric>
#include <cmath>
#include <climits>
#include <limits>
#include <cfloat>
#include <fstream>
using namespace std;

bool isleap (int year )
{
	return ( ( year % 4 == 0 ) && ( ( year % 100 != 0 ) || ( year % 400 == 0 ) ) );
}

int main()
{
	string str = "";
	vector < vector <int> > res;
	int size = 0;
	int i,j;

	while (getline (cin, str ) ){

		int a, b;
		stringstream ss(str);

		ss >> a >> b;

		if (a == 0 && b == 0){
			break;
		} // end if

		++size;
		res.resize(size);

		for (i = a; i <= b; ++i){
			if (isleap (i ) ){
				res[size - 1].push_back (i );
			} // end if
		}

		if (res[size - 1].empty() ){
			res[size - 1].push_back (-1 );
		} // end if

	} // end while

	for (i = 0; i < res.size(); ++i){
		for (j = 0; j < res[i].size(); ++j){
			if (res[i][j] == -1){
				cout << "NA" << endl;
				break;
			}else{
		 		cout << res[i][j] << endl;
			} // end if
		} // end for

		if (i != res.size() - 1){
			cout << endl;
		} // end for

	} // end loop
		
	return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
#define rep(i,N) for(int i=0;i<(N);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;
const long long MOD = 1e9 + 7;
const long long INF = 1e12;
const int inf = 1e9;
const int mod = 1e9+7;
typedef long long ll;
typedef pair<ll,int> P;
typedef set<int> S;
int main(){
    int a,b;
    cin>>a>>b;
    if(a<=5) cout<<0<<endl;
    else if(a<=12) cout<<b/2<<endl;
    else cout<<b<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
vector< int > Sum;
vector< bool > v;
int rec(const vector< int >& Color, int idx) {
  if(v[idx]) return(0);
  v[idx] = true;
  int cnt = 1;
  if(Color[(idx + Color.size() - 1) % Color.size()] >= 0) cnt += rec(Color, (idx + Color.size() - 1) % Color.size()); 
  if(Color[(idx + 1) % Color.size()] >= 0) cnt += rec(Color, (idx + 1) % Color.size());
  return(cnt);
}

int main() {
  int N, M;
  cin >> N >> M;
  vector< int > a(M), L(M);
  for(int i = 0; i < M; i++) {
    cin >> a[i] >> L[i];
  }
  vector< int > Color(N, -1);
  for(int i = 0; i < M; i++) {
    int begin = a[i], end = (a[i] + L[i] - 1) % N;
    while(begin != end){
      Color[begin] = i;
      begin = (begin + 1) % N;
    }
    Color[end] = i;
  }

  Sum.resize(N + 1, 0);
  v.resize(N + 1, false);
  for(int i = 0; i < N; i++) {
    if(Color[i] >= 0 && !v[i]) Sum[rec(Color, i)]++;
  }

  for(int i = N; i >= 0; i--) {
    if(Sum[i] > 0) cout << i << " " << Sum[i] << endl;
  }
}


Measured memory_bytes: 1200
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
using namespace std;                       
typedef long long ll;

 int main()
 {  ll t,t1=0,maxx=0,a,b,n;
    cin>>a>>b>>n;
   
         if(n>=b)
          {  t=(b-1)/b;
             cout<<(b-1)*a/b-a*t<<endl;
		  }
         else
         cout<<a*n/b-t*a<<endl;
	
    
}


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

int main(){
 int A, B ,T ;
  cin >> A >> B >> T;
  int s;
  s = (T / A) * B;
  
  cout << s << endl;
  
}

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

namespace ABC092A
{
    class Program
    {
        static void Main(string[] args)
        {
            int A = int.Parse(Console.ReadLine());
            int B = int.Parse(Console.ReadLine());
            int C = int.Parse(Console.ReadLine());
            int D = int.Parse(Console.ReadLine());

            int ansA = Math.Min(A, B);
            int ansB = Math.Min(C, D);

            Console.WriteLine(ansA + ansB);
            Console.ReadKey();
        }
    }
}


Measured memory_bytes: 11220
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n,k;
  cin >> n >> k;
  int arr[n];
  for(int i=0;i<n;i++) {
    cin >> arr[i];
  }
  sort(arr,arr+n);
  int sum=0;
  for(int i=0;i<k;i++) {
    sum += arr[i];
  }
  cout << sum << endl;
}


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

int main(){
    long long int n,k;
    cin>>n>>k;

    long long int h[n+1];

    for(int i=1;i<=n;i++)
        cin>>h[i];


    long long int cost[n+1];
    cost[1]=0;
    long long ans;



    for(int i=2;i<=n;i++){
         int z=i-k;
         if(z<=0)
            z=1;

         for(int j=i-1;j>=z;j--){
               long long k=abs(h[i]-h[j])+cost[j];

               if(j==i-1)
                ans=k;

               else
                 ans=min(ans,k);

         }


         cost[i]=ans;

    }

    cout<<ans<<endl;

}


Measured memory_bytes: 1792
/* 実行時間1s制限の場合
  10^6 1,000,000   : 余裕をもって間に合う
  10^7 10,000,000  : おそらく間に合う
  10^8 100,000,000 : 非常にシンプルな処理でないと厳しい
 */
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#include <bits/stdc++.h>
using namespace std;

typedef long long ll; // long longはデータモデル(LLP64, LP64, ...)によらず64bit.
ll gcd(ll a, ll b) {return b ? gcd(b, a%b) : a;}  // Greatest Common Divisor ユークリッドの互除法（aが長辺）
ll lcm(ll a, ll b) {return a/gcd(a,b)*b;}          // Least Commont Multiple オーバーフローしないように先に割る

const ll INF = LONG_MAX;
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()
{
#ifdef LOCAL
    // 以降 cin の入力元が 'xxx.txt' になる
    std::ifstream in("a.txt");
    std::cin.rdbuf(in.rdbuf());
#endif

    string s, t;
    cin >> s >> t;

    int ans = 0;
    rep(i, 3)
    {
        if (s[i] == t[i])
        {
            ans++;
        }
    }
    cout << ans;

    return 0;
}

/*
  - 1e9 : 10^9
  - vector
    vector<int> A(N);
    - loop
      for  (int i = 0; i < A.size(); i++) {}
      for  (int elem : A) {}
    - sort
      std::sort(v.begin(), v.end());  // 昇順
      std::sort(v.begin(), v.end(), std::greater<int>()); //降順
      - vector<vector<int>> cnt(h, vector<int>(w))
  - pair
    - pairのソートの定義 : firstが優先的に比較。同じだったらsecond。
  - map
    - for (auto x : map) {}  // x.first:key  x.second:value.
  - string
    - loop
      for (char& c : s) {}
 */



Measured memory_bytes: 256
#include <stdio.h>

int insertSort( int * Arr, int No );

int main(void)
{
	int No = 0;
	int Arr[100] = {};
	int i = 0;
	
	scanf( "%d", &No );
	
	for ( i = 0; i < No; i++ ) {
		scanf( "%d ", &Arr[i] );
	}
	
	insertionSort( Arr, No );
	
	return 0;
}

int insertionSort( int * Arr, int No ) {
	int i = 0;
	int j = 0;
	int v = 0;
	
	for ( i = 1; i < No; i++ ) {
		for ( j = 0; j < No-1; j++ ) {
			printf("%d ", Arr[j]);
		}
		printf("%d\n", Arr[j]);
		v = Arr[i];
		j = i-1;
		while ( j >= 0 && Arr[j] > v ) {
			Arr[j+1] = Arr[j];
			j--;
		}
		Arr[j+1] = v;
	}
	for ( j = 0; j < No-1; j++ ) {
		printf("%d ", Arr[j]);
	}
	printf("%d\n", Arr[j]);
	return 0;
}



Measured memory_bytes: 2104
#include <iostream>
#include <cstring>
#include <cstdio>

#define maxn 1000005

inline bool isp(int x) {
    if (x == 1) return false;
    for (register int i = 2; i * i <= x; ++i) {
        if (x % i == 0) return false;
    }
    return true;
}

long long plst[maxn];
bool nisp[maxn];
long long pcnt;

void iit() {
    for (long long i = 2; i < maxn; ++i) {
        if (!nisp[i]) {
            plst[++pcnt] = i;
        }
        for (long long j = 1; j <= pcnt && plst[j] * i < maxn; ++j) {
            nisp[plst[j] * i] = false;
            if (i % plst[j] == 0) break;
        }
    }
}

void handle(long long t) {
    int cur = 1;
    std::cout << t << ":";
    while (t >= 1 && cur <= pcnt) {
        if (t >= 1e6 && isp(t)) {
            std::cout << " " << t;
            break;
        }
        if (t % plst[cur] == 0) {
            t /= plst[cur];
            std::cout << " " << plst[cur];
        } else {
            cur++;
        }
    }
    std::cout << std::endl;
}

int main() {
    long long n;
    std::cin >> n;
    iit();
    handle(n);
}



Measured memory_bytes: 11868
N = int(input())
if N == 3:
    print(*[2, 5, 63])
elif N == 4:
    print(*[2, 5, 20, 63])
elif N == 5:
    print(*[2, 5, 20, 30, 63])
else:
    ans = []
    k = 0
    i = 0
    while True:
        ans.append(6 * k + 2)
        i += 1
        if i == N:
            break
        ans.append(6 * k + 3)
        i += 1
        if i == N:
            break
        ans.append(6 * k + 4)
        i += 1
        if i == N:
            break
        ans.append(6 * k + 6)
        i += 1
        if i == N:
            break
        k += 1
    if sum(ans) % 6 == 0:
        print(*ans)
    elif sum(ans) % 6 == 2:
        for j in range(N):
            if ans[j] == 8:
                ans.pop(j)
                break
        ans.append(30000)
        print(*ans)
    elif sum(ans) % 6 == 3:
        for j in range(N):
            if ans[j] == 9:
                ans.pop(j)
                break
        ans.append(30000)
        print(*ans)
    else:
        for j in range(N):
            if ans[j] == 9:
                ans.pop(j)
                break
        ans.append(29998)
        print(*ans)


Measured memory_bytes: 4572
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<cmath>
#include<iomanip>
using namespace std;

int main()
{
	long N;
	cin >> N;
	
	long A[N], buka[N];
	for(int i = 1; i < N; i++){
		cin >> A[i];
	}
	for(int i = 0; i < N; i++){
		buka[i] = 0;
	}
	
	for(int i = 1; i < N; i++){
		buka[A[i] - 1]++;
	}
	
	for(int i = 0; i < N; i++){
		cout << buka[i] << endl;
	}
	return 0;
	

}

Measured memory_bytes: 6728
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rep_r(i,n) for(int i=((int)(n)-1);i>=0;--i)
#define FOR(i,m,n) for(int i=((int)(m));i<(int)(n);++i)
#define FOR_R(i,m,n) for(int i=((int)(m)-1);i>=(int)(n);--i)
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define INF 2e9
#define LLINF 11e16
 
using namespace std;
 
typedef long long ll;

int main(){
	int K, X;
	cin >> K >> X;
	
	FOR(i, X - K + 1, X + K) cout << i << " ";
	
	return 0;
}

Measured memory_bytes: 256
from collections import Counter

mod = 998244353

N, *D = map(int, open(0).read().split())

C = Counter(D)
if D[0] != 0 or C[0] != 1:
    print(0)
    quit()

ans = 1
for i in range(2, max(C.keys(), default=0) + 1):
    ans *= pow(C[i - 1], C[i], mod)
    ans %= mod

print(ans)


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

#define for_(i,a,b) for(int i=(a);i<(b);++i)
#define for_rev(i,a,b) for(int i=(a);i>=(b);--i)

typedef vector< int > Ary;
typedef vector< Ary > Mat;

struct Edge { int to, c; };

void maxUpdate(int& a, int b) { a = max(a, b); }

void mul(Mat& res, Mat& a, Mat& b) {
	int N = a.size();
	res = a;
	
	for_(i,0,N) for_(j,0,N) for_(k,0,N) {
		if (a[i][k] >= 0 && b[k][j] >= 0) maxUpdate(res[i][j], a[i][k] + b[k][j]);
	}
}

int V, K, E, dp[155][155], prv[155][155];
vector< vector< Edge > > adj;

void restore(int step, int v) {
	int c = step;
	vector< int > path;
	
	while (v != -1) {
		path.push_back(v);
		v = prv[c--][v];
	}
	
	reverse(path.begin(), path.end());
	for_(i,0,step+1) cout << path[i] << (i < step ? " " : "\n");
}

bool shortPhase() {
	memset(dp, -1, sizeof(dp));
	memset(prv, -1, sizeof(prv));
	
	for_(v,0,V) dp[0][v] = 0;
	
	int max_score = -1, step = -1, terminal = -1;
	
	for_(i,0,150) {
		for_(v,0,V) {
			if (dp[i][v] == -1) continue;
		
			for (Edge e : adj[v]) {
				if (dp[i + 1][e.to] < dp[i][v] + e.c) {
					dp[i + 1][e.to] = dp[i][v] + e.c;
					prv[i + 1][e.to] = v;
					
					if (max_score < dp[i + 1][e.to]) {
						max_score = dp[i + 1][e.to];
						terminal = e.to;
					}
				}
			
			}
		}
		
		if (max_score >= K) {
			step = i + 1;
			break;
		}
	}
	
	if (max_score >= K) {
		cout << step << endl;
		restore(step, terminal);
		return true;
	}
	
	if (max_score == -1) {
		cout << -1 << endl;
		return true;
	}
	
	return false;
}

int calcMinStep() {
	Mat mat[21], ini(V, Ary(V, -1));
	
	for_(v,0,V) for (Edge e : adj[v]) {
		maxUpdate(ini[v][e.to], e.c);
	}
	
	mat[0] = ini;
	for_(i,0,20) mul(mat[i + 1], mat[i], mat[i]);
	
	int res = 0;
	
	Mat x(V, Ary(V, -1)), nx;
	for_(v,0,V) x[v][v] = 0;
	
	for_rev(h,19,0) {
		mul(nx, x, mat[h]);
		
		int max_score = 0;
		for_(u,0,V) for_(v,0,V) maxUpdate(max_score, nx[u][v]);
		
		if (max_score < K) {
			x = nx;
			res += 1 << h;
		}
	}
	
	return res + 1;
}

void solve() {
	if (!shortPhase()) {
		int ans = calcMinStep();
		cout << (ans > (int)1e6 ? -1 : ans) << endl;
	}
}

int main() {
	cin >> V >> E >> K;
	
	adj.assign(V, vector< Edge >());
	
	for_(i,0,E) {
		int u, v, c;
		cin >> u >> v >> c;
		adj[u].push_back(Edge{v, c});
	}
	
	solve();
}

Measured memory_bytes: 5532
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  int n; cin >> n;
  lint k; cin >> k;
  V<> a(n); for (auto&& e : a) cin >> e;
  V<> b(n); for (auto&& e : b) cin >> e;
  sort(begin(a), end(a));
  sort(rbegin(b), rend(b));
  auto chk = [&](lint x) -> bool {
    lint s = 0;
    for (int i = 0; i < n; ++i) {
      s += max<lint>(a[i] - x / b[i], 0);
    }
    return s <= k;
  };
  lint ng = -1, ok = 1e18;
  while (ok - ng > 1) {
    lint mid = (ng + ok) / 2;
    (chk(mid) ? ok : ng) = mid;
  }
  cout << ok << '\n';
}

Measured memory_bytes: 1920
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int H = sc.nextInt();
    int W = sc.nextInt();
    int h = sc.nextInt();
    int w = sc.nextInt();
    if((H % h == 0) && (W % w == 0)) {
      System.out.println("No");
    } else {
      System.out.println("Yes");
      int[][] ans = new int[H][W];
      if(H % h == 0) {
        for(int i = 0; i < H; i++) {
          for(int j = 0; j < W; j++) {
            if(j % w == 0) {
              ans[i][j] = 1000 * w - 1001;
            } else {
              ans[i][j] = -1000;
            }
          }
        }
      } else {
        for(int i = 0; i < H; i++) {
          for(int j = 0; j < W; j++) {
            if(i % h == 0) {
              ans[i][j] = 1000 * h - 1001; 
            } else {
              ans[i][j] = -1000;
            }
          }
        }
      }
      for(int i = 0; i < H; i++) {
        for(int j = 0; j < W; j++) {
          System.out.print(ans[i][j]);
          if(j < W - 1) {
            System.out.print(" ");
          } else {
            System.out.println();
          }
        }
      }
    }
  }
}

Measured memory_bytes: 60388
#include <stdio.h>

#define MAX (52)

int main(void) {
	char SUITS[] = "SHCD";
	char suit;
	int cards[MAX];
	int count, number;
	int i;
	
	for (i = 0; i < MAX; i++) {
		cards[i] = 1;
	}
	scanf("%d\n", &count);
	for (i = 0; i < count; i++) {
		scanf("%c %d\n", &suit, &number);
		switch (suit) {
		case 'H': number += 13; break;
		case 'C': number += 13 * 2; break;
		case 'D': number += 13 * 3; break;
		default: break;
		}
		cards[number - 1] = 0;
	}
	for (i = 0; i < MAX; i++) {
		if (cards[i]) {
			printf("%c %d\n", SUITS[i / 13], (i % 13) + 1);
		}
	}

	return 0;
}

Measured memory_bytes: 600
from math import floor, sqrt
 
N = int(input())
ans = 0
for o in range(1, N + 1, 2):
    cnt = 0
    for n in range(1, 1 + floor(sqrt(o))):
    	if o % n == 0:
            cnt += 2
    if cnt == 8:
        ans += 1
print(ans)

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

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep3(i,m,n) for(int (i)=m;(i)<=(n);(i)++)
#define rep3rev(i,m,n) for(int (i)=m;(i)>=(n);(i)--)
#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define eb emplace_back

using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using P = pair<int, int>;

void Main(){
    string s; cin >> s;
    int n = s.size();
    ll ans = 0, cnt = 0, tmpa = 0, tmpbc = 0;

    rep(i, n){
        if(s[i] == 'A'){
            tmpa++;
        }else if(s.substr(i, 2) == "BC"){
            tmpbc++;
            i++;
            cnt += tmpa;
        }else{
            ans += cnt;
            tmpa = 0;
            tmpbc = 0;
            cnt = 0;
        }
        // cout << i << ": " << cnt << " " << ans << endl;
    }
    cout << ans + cnt << endl;
    return;
}

int main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
    return 0;
}

Measured memory_bytes: 3748
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <string>
#include <stack>
#include <iomanip>
#include <numeric>
#include <queue>
#include <climits>
#include <complex>
#include <cmath>
#include <map>
using namespace std;
using ll = long long;
#define MOD 1000000007
#define INF 1LL << 59

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

    int arr[3];
    int r = 0, t = 0;
    char c;
    while (cin >> arr[0] >> c >> arr[1] >> c >> arr[2])
    {
        if (arr[0] == arr[1])
            t++;
        if (arr[0] * arr[0] + arr[1] * arr[1] == arr[2] * arr[2])
            r++;
    }

    cout << r << "\n"
         << t << endl;
    return 0;
}


Measured memory_bytes: 3080
from math import ceil, floor, log2
import sys

n, a = map(int, next(sys.stdin).strip().split())

t = n
for k in range(1, ceil(log2(n))):
    d = ceil(n ** (1 / k))
    l = 0
    r = k
    while l + 1 < r:
        c = (l + r) // 2
        if n <= (d - 1) ** (k - c) * d ** c:
            r = c
        else:
            l = c
    t = min(t, (d - 1) * (k - r) + d * r + (k - 1) * a)
print(t)


Measured memory_bytes: 3064
#include<iostream>
#include<vector>
#include<math.h>
#include<algorithm>
#include<memory>
#include<string>
typedef long long ll;
int main() {
	int n;
	ll a = 0;
	ll b = 0;
	ll c = 0;
	std::cin >> n;
	for (int i = 3; i <= n; i++) {
		for (int j = 2; j < i; j++) {
			for(int k = 1; k < j; k++){
				for (int l = k; l >= 1; l--) {
					if (i % l == 0 && j % l == 0 && k % l == 0) {
						a += l;
						break;
					}
				}
			}
		}
	}
	for (int i = 2; i <= n; i++) {
		for (int j = 1; j < i; j++) {
			for (int l = j; l >= 1; l--) {
				if (i % l==0 && j % l==0) {
					b += l;
					break;
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		c += i;
	}
	std::cout << a * 6 + b * 6 + c << std::endl;
	return 0;
}

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

using namespace std;

#define int long long

const int INF = 1e18;

vector <vector <int> > g;
vector <int> vis;
vector <bool> used;

void dfs(int v) {
    vis.push_back(v);
    used[v] = true;
    for (int to : g[v]) {
        if (!used[to]) {
            dfs(to);
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    g.resize(n);
    used.resize(n, false);
    vector <int> p(n);
    for (int& it : p) {
        cin >> it;
        --it;
    }
    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        --x; --y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        if (!used[i]) {
            vis.clear();
            dfs(i);
            set <int> s;
            for (int it : vis) {
                s.insert(p[it]);
            }
            for (int it : vis) {
                if (s.count(it)) {
                    ++ans;
                }
            }
        }
    }
    cout << ans << "\n";
    return 0;
}

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

using namespace std;

int main(void){
  int n;
  cin >> n;
  int count = 0;
  int count2 = 0;
  
  for(int i = 0;i < n;i++){
    int x; cin >> x;
    if(x % 4 == 0) count++;
    else if(x % 2 == 0) count2++;
  }
  
  cout << (count+count2/2 >= n/2 ? "Yes" : "No") << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <complex>
#include <vector>
#include<limits>
#include<iomanip>
#include<cassert>

using namespace std;

typedef long long ll;
typedef pair<int, int> pint;
typedef pair<ll, ll> pll;

#define debug(x) cout << #x << " = " << (x) << endl;
#define rep(i, n) for(int i = 0;i < n;i++)
#define repr(i, n) for(int i = n-1;i >= 0;i--)
#define pb push_back
#define mp make_pair
#define F first
#define S second

const long double pi = 3.141592653589793;
const int mod = 998244353;


int main() {

// freopen("input.in","r",stdin);
// freopen("output.out","w",stdout);

 ll n,m,k;cin>>n>>m>>k;
 vector<ll> A(n), B(m);
 rep(i,n)cin>>A[i];
 rep(i,m)cin>>B[i];

 for(int i = 1;i < n;i++) A[i] += A[i-1];
 for(int j = 1;j < m;j++) B[j] += B[j-1];

 int ans = 0;
 for(int i = 0;i <= n;i++) {
   ll sum = 0;
   if(i > 0) sum += A[i-1];
   if(sum > k) break;

   sum = k - sum;
   int cnt = upper_bound(B.begin(), B.end(), sum) - B.begin();
   ans = max(ans, i + cnt);
 }
 cout<<ans;

 return 0;
}


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

int main() {
  string S;
  cin >> S;
  if (S[0] == S[1] || S[1] == S[2] || S[2] == S[3] || S[3] == S[4]) puts("Bad");
  else puts("Good");

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
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; }

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ for(auto it : P) { s << "<" << it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ for(auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s << endl; }


const long long INF = 1LL<<60;
int N;
vector<long long> A;

long long solve() {
    vector<long long> left(N+1, 0), right(N+1, 0);
    for (int i = 0; i < N; ++i) {
        if (i % 2 == 0) {
            left[i+1] = left[i] + A[i];
            right[i+1] = right[i] + A[N-i-1];
        }
        else left[i+1] = left[i], right[i+1] = right[i];
    }
    vector<long long> dp(N+1, -INF);
    dp[0] = 0;
    for (int i = 2; i <= N; i += 2) {
        chmax(dp[i], dp[i-2] + A[i-1]);
        chmax(dp[i], left[i-2] + max(A[i-1], A[i-2]));
    }

    if (N % 2 == 0) return dp[N];
    long long res = -INF;
    for (int i = 0; i <= N; i += 2) {
        chmax(res, dp[i] + right[N-i-1]);
    }

    //COUT(left); COUT(right); COUT(dp);

    return res;
}

int main() {
    while (cin >> N) {
        A.resize(N);
        for (int i = 0; i < N; ++i) cin >> A[i];
        cout << solve() << endl;
    }
}

















Measured memory_bytes: 9536
//For higher stack size use g++ -O2 -std=c++11 -Wall -Wl,--stack=268435456 a.cpp -o a.exe in cmd
    #include <bits/stdc++.h>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <cstring>
    #include <chrono>
    #include <complex>
    #define ll long long
    #define ld long double
    #define vi vector<int>
    #define vll vector<ll>
    #define vvi vector < vi >
    #define pii pair<int,int>
    #define pll pair<long long, long long>
    #define mod 1000000007
    #define inf 1000000000000000001;
    #define all(c) c.begin(),c.end()
    #define mp(x,y) make_pair(x,y)
    #define mem(a,val) memset(a,val,sizeof(a))
    #define eb emplace_back
    #define pb push_back
    #define f first
    #define s second
    
    using namespace std;
    int main()
    {
        std::ios::sync_with_stdio(false);
        int T;
        T=1;
        // cin.ignore(); must be there when using getline(cin, s)
        while(T--)
        {
            ll a,p;
            cin>>a>>p;
            p=p+3*a;
            int ans=p/2;
            cout<<ans<<endl;
        }
        return 0;
    }


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <queue>
#define ri register int 
#define ll long long 
#define ull unsigned long long 
using std::min;
using std::max;
using std::lower_bound;
using namespace __gnu_pbds;
template <class T>inline void read(T &x){
    x=0;int ne=0;char c;
    while(!isdigit(c=getchar()))ne=c=='-';
    x=c-48;
    while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
    x=ne?-x:x;return ;
}
const int maxn=200005;
const int inf=0x7fffffff;
int n,nn,a[maxn],b[maxn],c[maxn],mx=-inf,mi=inf;
ll sum[maxn<<2];
inline void update(int x,int d){for(;x<=nn;x+=x&(-x))sum[x]+=d;}
inline ll query(int x){ll ans=0;for(;x;x-=x&(-x))ans+=sum[x];return ans;}
inline ll chk(int k){
    ll ans=0;
    b[0]=0;
    for(ri i=1;i<=n;i++){
        b[i]=b[i-1]+((a[i]<=k)?1:-1);
        c[i]=b[i];
        ans+=(b[i]>0);
    }
    std::sort(c+1,c+1+n);
    nn=std::unique(c+1,c+1+n)-(c+1);
    memset(sum,0,sizeof(sum));
    for(ri i=1;i<=n;i++){
    	b[i]=lower_bound(c+1,c+1+nn,b[i])-c;
        ans+=query(b[i]-1);
        update(b[i],1);
    }
    return ans;
}
int main(){
    read(n);
    for(ri i=1;i<=n;i++){
        read(a[i]);
        mi=min(mi,a[i]),mx=max(mx,a[i]);
    }
    int L=mi,R=mx,mid,ans;
	ll lim=1ll*n*(n+1)/4+1;
    while(L<=R){
        mid=(L+R)>>1;
        if(chk(mid)>=lim)ans=mid,R=mid-1;
        else L=mid+1;
    }
    printf("%d\n",ans);
    return 0;
}

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

int main() {
    int n;

    while(cin >> n) {
        int count = 0;
        for (int i = 0; i <= 9; ++i) {
            if ((n - i) / 3.0 > 9) continue;
            if ((n - i) < 0) continue;
            for (int j = 0; j <= 9; ++j) {
                if ((n - (i+j)) / 2.0 > 9) continue;
                if ((n - (i+j)) < 0) continue;
                for (int k = 0; k <= 9; ++k) {
                    if ((n - (i+j+k)) > 9) continue;
                    if ((n - (i+j+k)) < 0) continue;
                    count++;
                }
            }
        }
        cout << count << endl;
    }

    return 0;
}

Measured memory_bytes: 1160
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>

#define debug(x) cout << #x << "==" << x << endl;


const int INF = 1e+8;

using namespace std;

template<typename T>
vector<vector<T>> make_2d_vector(size_t rows, size_t cols, T init)
{ return vector< vector<T> >(rows, vector<T>(cols, init)); }


//??\???
#define MAX_N 100
#define MAX_W 10000
// int N, W_LIM;
// int V[MAX_N], W[MAX_N];

// // dp table
// int dp[MAX_N][MAX_W];
// bool checked[MAX_N][MAX_W];


int main() {
  ios::sync_with_stdio(false);

  int N, W;
  cin >> N >> W;

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

  // dp[i][j] := i???????????§????????£???????????????????¨????j???????????????????????§???;
  // dp[i][j] := 
  //   0          (if i == 0 or j == )0
  //   dp[i-1][j] (if w[i-1] > j)
  //   max( dp[i-1][j], v[i-1] + dp[i-1][j-w[i-1]] )
  vector< vector<int> > dp = make_2d_vector(N+1, W+1, 0);
  for(int i = 1; i <= N; i++) {
    for(int j = 0; j <= W; j++) {
      if( j < w[i-1] ) dp[i][j] = dp[i-1][j];
      else              dp[i][j] = max( dp[i-1][j], v[i-1] + dp[i-1][j-w[i-1]] );
    }
  }

  // for(int i = 0; i <= N; i++) {
  //   for(int j = 0; j <= W; j++) {
  //     cout << dp[i][j] << " ";
  //   }
  //   cout << "\n";
  // }

  cout << dp[N][W] << "\n";

  return 0;
}

Measured memory_bytes: 6764
//Union Find
#include<bits/stdc++.h>
using namespace std;
class DisjointSet{
    public:
    
    vector<int> rank,p;
    DisjointSet(){}
    DisjointSet(int size){
        rank.resize(size,0);
        p.resize(size,0);
        for(int i=0;i<size;i++) makeSet(i);
    }

    void makeSet(int x){
        p[x]=x;
        rank[x]=0;
    }

    bool same(int x,int y){
        return findSet(x)==findSet(y);
    }

    void unite(int x,int y){
        link(findSet(x),findSet(y));
    }

    void link(int x,int y){
        if(rank[x]>rank[y]){
            p[y]=x;
        }else{
            p[x]=y;
            if(rank[x]==rank[y]){
                rank[y]++;
            }
        }
    }

    int findSet(int x){
        if(x!=p[x]){
            p[x]=findSet(p[x]);
        }
        return p[x];
    }
};

int main(){
    int n,a,b,q;
    int t;
    cin>>n>>q;
    DisjointSet ds=DisjointSet(n);
    for(int i=0;i<q;i++){
        cin>>t>>a>>b;
        if(t==0) ds.unite(a,b);
        else if(t==1){
            if(ds.same(a,b)) cout<<1<<'\n';
            else cout<<0<<'\n';
        }
    }
    return 0;
}


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

int h, w, d;
char m[100][100];

bool checkRange(int x, int y)
{
	return (0 <= x && x < w) && (0 <= y && y < h);
}

int calcTate()
{
	int cnt = 0;

	for (int y = 0; y < h; y++)
	{
		for (int x = 0; x < w; x++)
		{
			for (int i = 0; i < d; i++)
			{
				if (!checkRange(x, y + i)) break;
				if (m[x][y + i] == '#') break;
				if (i == d - 1) cnt++;
			}
		}
	}
	return cnt;
}
int calcYoko()
{
	int cnt = 0;

	for (int y = 0; y < h; y++)
	{
		for (int x = 0; x < w; x++)
		{
			for (int i = 0; i < d; i++)
			{
				if (!checkRange(x + i, y)) break;
				if (m[x + i][y] == '#') break;
				if (i == d - 1) cnt++;
			}
		}
	}
	return cnt;
}

int main()
{
	cin >> h >> w >> d;
	for (int y = 0; y < h; y++)
	{
		for (int x = 0; x < w; x++)
		{
			cin >> m[x][y];
		}
	}
	cout << calcTate() + calcYoko() << endl;

	return 0;
}

Measured memory_bytes: 3100
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    H,W=map(int,input().split())
    print('#'*(W+2))
    for _ in range(H):
        print('#'+input()+'#')
    print('#'*(W+2))

if __name__ == '__main__':
    main()


Measured memory_bytes: 38256
///  ||====================================================================||
///  ||                Name: Ezaz Hossain                                  ||
///  ||                CodeChef: harith_0                                  ||
///  ||                NIT Durgapur                                        ||
///  ||====================================================================||

#include<bits/stdc++.h>
#define ll long long int
#define mod 1000000007
#define MAX 10003
#define pb push_back
// #define mp make_pair
#define F first
#define S second
#define mem(x,y) memset(x,y,sizeof(x))
#define lcm(a,b) (a*b)/__gcd(a,b)
#define set_bit_count(x) __builtin_popcount(x)
#define str_rev(str) reverse(str.begin(),str.end())
#define loop(i,x,y) for(ll i=x;i<y;i++)
#define rloop(i,x,y) for(ll i=x-1;i>=y;i--)
#define fastio ios_base::sync_with_stdio(false); cout.tie(NULL);
using namespace std;
int main()
{
  long long int x;
  long long int r = 100, count = 0;
  cin >> x;
  while(r<x)
  {
    r = r + (r/100);
    count++;
  }
         cout << count << endl;
}

Measured memory_bytes: 3596
N,X,Y = map(int, input().split())
numbers = [0 for i in range(N-1)]
for i in range(N-1):
    for j in range(i+1,N):
        p = i+1
        q = j+1
        k = min(abs(X-p)+1+abs(Y-q),q-p)
        
        numbers[k-1] += 1


for i in range(N-1):
    print(numbers[i])


Measured memory_bytes: 3444
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<string> vs;
ll llmax = LLONG_MAX;
string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
string alp = "abcdefghijklmnopqrstuvwxyz";
vi d1 = {1, 0, -1, 0}, d2 = {0, 1, 0, -1};
void Yes() {cout << "Yes" << endl;}
void No() {cout << "No" << endl;}
void YES() {cout << "YES" << endl;}
void NO() {cout << "NO" << endl;}
void neg() {cout << -1 << endl;}

int main() {
  ll n, ww;
  cin >> n >> ww;
  vll w(n), v(n);
  for (ll i = 0; i < n; i++) cin >> w[i] >> v[i];
  vll dp(100001);
  vector<vll> check(100001, vll(n));
  for (ll i = 1; i <= ww; i++) {
    dp[i] = dp[i - 1];
    ll memo = -1;
    for (ll j = 0; j < n; j++) {
      if (i < w[j]) continue;
      if (check[i - w[j]][j] == 1) continue;
      if (dp[i] < dp[i - w[j]] + v[j]) {
        dp[i] = dp[i - w[j]] + v[j];
        memo = j;
      }
    }
    if (memo != -1) {
      check[i] = check[i - w[memo]];
      check[i][memo] = 1;
    }
    else check[i] = check[i-1];
  }
  cout << dp[ww] << endl;
}


Measured memory_bytes: 83072
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int S = scan.nextInt();
		scan.close();
		if(0 <= S && S < 86400)
		System.out.println(S/3600+":"+S%3600/60+":"+S%60);

	}

}

Measured memory_bytes: 26212
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i) 
#define PI acos(-1)

using namespace std;
using ll = long long;
using P = pair<int, int>;
using LP = pair<ll, ll>;

struct DisjointSet {
private:
    vector<int> par;
    vector<int> rank;

public:
    DisjointSet(int n) {
        par = vector<int>(n);
        rep(i, n) par[i] = i;
        rank = vector<int>(n);
    }

    int find(int i) {
        if (par[i] == i) return i;
        int p = find(par[i]);
        par[i] = p;
        return p;
    }

    bool joint(int i, int j) {
        int pi = find(i);
        int pj = find(j);
        if (pi == pj) return false;

        if (rank[pi] < rank[pj]) this->par[pi] = pj;
        else if (rank[pj] < rank[pi]) this->par[pj] = pi;
        else {
            this->par[pi] = pj;
            rank[pj]++;
        }
        return true;
    }
};

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

    int n;
    cin>>n;
    priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> q;
    rep(i, n) {
        rep(j, n) {
            int w;
            cin>>w;
            if (w == -1) continue;

            vector<int> v = {w, i, j};
            q.push(v);
        }
    }
    DisjointSet ds(n);
    ll ans = 0;
    while (!q.empty()) {
        vector<int> v = q.top(); q.pop();
        int w = v[0];
        int v1 = v[1];
        int v2 = v[2];
        if (ds.joint(v1, v2)) ans += w;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 3372
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define rep2(i,n) for(int i=0;i<=n;i++)
#define repr(i,a,n) for(int i=a;i<n;i++)
#define all(a) a.begin(),a.end()
#define P pair<long long,long long>
#define double long double
#define vector2(a,b,c) vector<vector<int>> a(b/*縦！w*/,vector<int>(c/*横！w*/))
#define INF 1e10
#define MOD 1e9+7
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 Graph = vector<vector<int>>;
signed main(){
  int a,b;
  cin>>a>>b;
  if(a+b>=24)
    cout<<a+b-24<<endl;
  else
    cout<<a+b<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
//mt19937 mrand(random_device{}());
const ll mod=1000000007;
//int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

int n;
char s[10];
map<string,int> cnt;

int main() {
	scanf("%d",&n);
	rep(i,0,n) {
		string S;
		scanf("%s",s);
		rep(i,0,strlen(s)) S+=s[i];
		cnt[S]++;
	}
	for (string p:{"AC","WA","TLE","RE"}) printf("%s x %d\n",p.c_str(),cnt[p]);
}

Measured memory_bytes: 3760
// Written By Mahtab Tanim
#include<bits/stdc++.h>
using namespace std;
#define MP ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define nl "\n"
#define End return 0
#define ll long long int
#define mp make_pair
#define pb push_back
#define ull unsigned long long int
#define pi acos(-1)
#define forn(i,a,b) for (int i=a;i<=b;i++)
int main()
{
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    int i=1;
    bool t=false, f=false;
    while(a&&c)
    {
        if(i%2)
        {
            c=c-b;
            if(c<=0)
            {
                f=true;
                break;
            }
        }
        else
        {
            a=a-d;
            if(a<=0)
            {
                t=true;
                break;
            }
        }
        i++;
    }
    if(t)
        cout<<"No"<<endl;
    else if(f)
        cout<<"Yes"<<endl;

    End;
}


Measured memory_bytes: 3632
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        #[cfg(debug_assertions)]
        writeln!(&mut std::io::stderr(), concat!("[DEBUG] ", $(stringify!($a), "={:?} "),*), $($a),*);
    }
}

#[allow(unused_imports)]
use std::cmp::{min, max};
#[allow(unused_imports)]
use std::io::{stdout, stdin, BufWriter, Write};

fn main() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (write!(out,$($format)*).unwrap());
    }

    input!{
      n: usize,
      mut s: chars,
    }
    s.dedup();
    puts!("{}\n", s.len());
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
int main()
{
  string s;
  cin>>s;
  int ans=0,j,temp;
  for(int i=0;i<3;i++)
  {
    temp=0;
    if(s[i]=='R')
    {
      for(j=i;j<3;j++)
      {
        if(s[j]=='S')
          break;
        else
          temp++;
      }
      j=i;
      ans=max(ans,temp);
    }
    
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 3588