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

int n , w ;
int weight[ 101 ] , price[ 101 ] ;
long long dp[ 101 ][ 100001 ] ;

ll solve( int i , int j )
{
    if( i == 0 || j == 0 )
        return 0 ;

    if( dp[ i ][ j ] != -1 )
        return dp[ i ][ j ] ;

    ll ans1 = 0 ;
    if( weight[ i ] <= j )
        ans1 = solve( i - 1 , j - weight[ i ] ) + price[ i ] ;

    ll ans2 = solve( i - 1 , j ) ;

    dp[ i ][ j ] = max( ans1 , ans2 ) ;
    return dp[ i ][ j ] ;

}
int main()
{
    cin >> n >> w ;

    memset( dp , -1 , sizeof(dp) ) ;

    for( int i = 1 ; i <= n ; i ++ )
        cin >> weight[ i ] , cin >> price[ i ] ;
    cout << solve( n , w ) ;
}



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

d = {}
for i in range(1,N+1):
  d[i] = 0

for i in range(M):
  a, b = A[i][0], A[i][1]
  d[a] += A[i].count(a)
  d[b] += A[i].count(b)

for k, v in d.items():
  print(v)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class T, class U> using Pa = pair<T, U>;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int H,W,K;
    cin >> H >> W >> K;
    vvec<int> S(H+1,vec<int>(W+1));
    vvec<int> F(H,vec<int>(W));
    for(int i=0;i<H;i++) for(int j=0;j<W;j++){
        char c;
        cin >> c;
        F[i][j] = c-'0';
        S[i+1][j+1] = F[i][j];
    }
    for(int i=1;i<=H;i++) for(int j=1;j<=W;j++) S[i][j] += S[i][j-1];
    for(int i=1;i<=H;i++) for(int j=1;j<=W;j++) S[i][j] += S[i-1][j];

    auto sum = [&](int r1,int c1,int r2,int c2){
        return S[r2+1][c2+1]-S[r2+1][c1]-S[r1][c2+1]+S[r1][c1];
    };

    int ans = 1e9;
    for(int S=0;S<(1<<(H-1));S++){
        vec<int> cut = {0};
        for(int i=0;i<H-1;i++){
            if(S&(1<<i)) cut.push_back(i+1);
        }
        cut.push_back(H);
        int now = __builtin_popcount(S);
        int last = 0;
        int n = cut.size();
        bool valid = true;
        for(int j=1;j<=W;j++){
            bool need = false;
            for(int i=0;i<n-1;i++){
                if(sum(cut[i],j-1,cut[i+1]-1,j-1)>K) valid = false;
            }
            if(j==W) continue;
            for(int i=0;i<n-1;i++){
                if(sum(cut[i],last,cut[i+1]-1,j)>K){
                    need = true;
                    last = j;
                    break;
                }
            }
            now += need;
        }
        if(valid) ans = min(ans,now);
    }
    cout << ans << "\n";
}

Measured memory_bytes: 384
#include <iostream>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <string>
#include <math.h>
#include <iomanip>
using namespace std;

const long double PI = 3.14159265358979;

int main(void) {

	long long int a, b, h, m;
	cin >> a >> b >> h >> m;

	long double hrad = (h * 60 + m) * PI / 360;
	long double mrad = (m * PI) / 30;

	long double rad = abs(hrad - mrad);
	if (rad >= PI) rad = 2 * PI - rad;

	long long int aa = a * a;
	long long int bb = b * b;

	long double c = sqrt(aa + bb - (2 * a * b * cos(rad)));

	cout << fixed << setprecision(20) << c << endl;
	return 0;
}

Measured memory_bytes: 4120
#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = (ll)(1e9+7);
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
#ifdef LOCAL
#define debug(x) cerr << #x << ": " << x << endl
#else
#define debug(x)
#endif
int dx[4]={ 1,0,-1,0 };
int dy[4]={ 0,1,0,-1 };

long long power(long long x, long long N, long long P){
	if(N == 0) return 1LL;
	if(N == 1) return x;
	long long tmp = power(x, N/2, P);
	if(N%2 == 0) return tmp * tmp % P;
	else return tmp * tmp % P * x % P;
}

ll N, P;
string S;

ll cnt[10005] ={};
ll ans = 0;

signed main(){
	cin >> N >> P >> S;
	if(P == 2){
		ll ans = 0;
		rep(i, N){
			if((S[i]-'0')%2 == 0){
				ans += i+1;
			}
		}
		cout << ans << endl;
		return 0;
	}
	if(P == 5){
		ll ans = 0;
		rep(i, N){
			if((S[i]-'0')%5 == 0){
				ans += i+1;
			}
		}
		cout << ans << endl;
		return 0;
	}
	cnt[0] = 1;
	ll now = 0;
	rep(i, N){
		now *= 10;
		now += S[i]-'0';
		now %= P;
		cnt[(now*power(10LL,N-1-i, P))%P]++;
		//cout << (now*power(10, N-1-i, P))%P << " ";
	}
	//cout << endl;
	rep(i, P){
		ans += (cnt[i]-1)*cnt[i]/2;
	}
	cout << ans << endl;
}

/*
10 37
5739058599
*/

Measured memory_bytes: 768
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)

using namespace std;
typedef long long int ll;
typedef pair <int, int> P;
const ll MOD=1000000007;
int N;
vector<int> E[100000];
ll dp[100000][2];
bool used[100000];
void dfs(int x){
    used[x]=1;
    if(E[x].size()==1){
        dp[x][0]=1;
        dp[x][1]=1;
    }
    else{
        dp[x][0]=1;
        dp[x][1]=1;
        rep(i,0,E[x].size()){
            if(!used[E[x][i]]){
                dfs(E[x][i]);
                dp[x][0]*=dp[E[x][i]][1];
                dp[x][0]%=MOD;
                dp[x][1]*=dp[E[x][i]][0]+dp[E[x][i]][1];
                dp[x][1]%=MOD;
            }
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>N;
    rep(i,0,N-1){
        int a,b;
        cin>>a>>b;
        E[a-1].push_back(b-1);
        E[b-1].push_back(a-1);
    }
    if(N==2){
        cout <<3<<"\n";
    }
    else{
        if(E[0].size()==1){
            dfs(E[0][0]);
            cout <<(dp[E[0][0]][0]+dp[E[0][0]][1])%MOD<<"\n";
        }
        else{
            dfs(0);
            cout <<(dp[0][0]+dp[0][1])%MOD<<"\n";
        }
    }
}


Measured memory_bytes: 12928
#include <iostream>
#include <cstdlib>
#include <bitset>
#include <iomanip>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
#include <sstream>
#include <math.h>

using namespace std;

#define ll long long int
#define vecll vector<long long>
#define vec2ll vector<vector<long long>>
#define vecchar vector<char>
#define vecstr vector<string>
#define vecbool vector<bool>
#define vec2bool vector<vector<bool>>
#define vecpairll vector<pair<long long,long long>>
#define forll(s,a,b) for(ll s = a;s < b;s++)
#define forllde(s,a) for(ll s = a;s > 0;s--)

#define Pi 3.1415926535897932384626

int main() {
	ll n, ans = 0;
	string s;
	bool flag = false;

	cin >> n;

	cout << n + n*n + n*n*n;
}


Measured memory_bytes: 3600
from collections import deque
H,W,K=map(int,input().split())
A=[list(input())for _ in [0]*H]
for i,a in enumerate(A):
	if"S"in a:y,x=i,a.index("S")
d=1e9
Q=deque([(1,y,x)])
while Q:
	c,i,j=Q.popleft()
	d=min(d,i,j,H-i-1,W-j-1)
	if c>K:continue
	for h,w in((i+1,j),(i,j+1),(i-1,j),(i,j-1)):
		if 0<=h<H and 0<=w<W and A[h][w]==".":
			A[h][w]=""
			Q+=[(c+1,h,w)]
print(1-(-d//K))

Measured memory_bytes: 75356
n = int(input())
l = [int(input()) for _ in range(n)]
not_ten = [i for i in l if i % 10 != 0]
if not_ten:
    ttl = sum(l)
    if ttl % 10 != 0:
        print(ttl)
    else:
        print(ttl - min(not_ten))
else:
    print(0)

Measured memory_bytes: 3060
while True:
    n = int(input())
    if n == 0:
        break
    t_list = []
    for i in range(n):
        t_list.append(int(input()))
    t_list.sort()
    ans = 0
    for i in range(n - 1):
        ans += t_list[i]*(n - i -1)
    print(ans)



Measured memory_bytes: 5728
#include <stdio.h>

int main(){
  int n, s, e, in, out, i, f;
  int line[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 5, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

  scanf("%d", &n);
  while(n--){
    scanf("%d%d", &in, &out);
    s = e = -1;
    for(i = 0; i < 25; ++i){
      if(line[i] == in) s = i;
      if(line[i] == out && s != -1){ e = i; break;}
    }

    for(i = s; i <= e; ++i) printf(i == s ? "%d" : " %d", line[i]);
    puts("");
  }
  return 0;
}

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

using namespace std;

void solve()
{
	int n; cin>>n;
	string s[2];
	{
		string t; cin>>t;
		s[0]='N'+t.substr(0,2*n)+'N';
		s[1]='N'+t.substr(2*n)+'N';
	}
	
	vector<vector<int>> dp(2,vector<int>(n+1));
	
	if(s[1][1]=='Y'){
		dp[0][0]=3;
		dp[1][0]=2;
	}
	else if(s[0][1]=='Y')
		dp[0][0]=dp[1][0]=1;
	else
		dp[1][0]=1;
	
	for(int i=1;i<=n;i++){
		if((s[0][i*2]=='Y' || s[0][i*2+1]=='Y')
		&& (s[1][i*2]=='Y' || s[1][i*2+1]=='Y')){
			dp[0][i]=min(dp[0][i-1]+3,dp[1][i-1]+2);
			dp[1][i]=min(dp[0][i-1]+2,dp[1][i-1]+2);
		}
		else if(s[1][i*2]=='Y' || s[1][i*2+1]=='Y'){
			dp[0][i]=min(dp[0][i-1]+3,dp[1][i-1]+2);
			dp[1][i]=min(dp[0][i-1]+2,dp[1][i-1]+1);
		}
		else if(s[0][i*2]=='Y' || s[0][i*2+1]=='Y'){
			dp[0][i]=min(dp[0][i-1]+1,dp[1][i-1]+1);
			dp[1][i]=min(dp[0][i-1]+1,dp[1][i-1]+1);
		}
		else{
			dp[0][i]=min(dp[0][i-1],dp[1][i-1]+1);
			dp[1][i]=min(dp[0][i-1]+1,dp[1][i-1]);
		}
		dp[0][i]++; dp[1][i]++;
	}
	
	cout<<dp[0][n]<<endl;
}

int main()
{
	int tc; cin>>tc;
	while(tc--)
		solve();
	return 0;
}

Measured memory_bytes: 1376
from collections import Counter
from sys import stdin

def main():
    N = int(input())
    S = input()

    cnt = Counter(S)
    ans = 1
    for i in cnt.values():
        ans *= i + 1
        ans %= 1000000007
    print(ans - 1)

input = lambda: stdin.readline().rstrip()
main()


Measured memory_bytes: 3480
#pragma GCC optimize("Ofast","unroll-loops")
#pragma GCC push_options
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
#include <xmmintrin.h>
#include <immintrin.h>
using namespace::std;
__attribute__((constructor))void init(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#include<ext/pb_ds/tag_and_trait.hpp>
// #include <boost/multiprecision/cpp_dec_float.hpp>
// #include <boost/multiprecision/cpp_int.hpp>
// namespace mp = boost::multiprecision;
// typedef mp::number<mp::cpp_dec_float<0>> cdouble;
// typedef mp::cpp_int cint;
template<typename T>using pbds=__gnu_pbds::tree<T,__gnu_pbds::null_type,less<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>;
template<typename T>using pbds_map=__gnu_pbds::tree<T,T,less<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>;
template<typename T,typename E>using hash_map=__gnu_pbds::gp_hash_table<T,E>;
template<typename T>using pqueue =__gnu_pbds::priority_queue<T, greater<T>,__gnu_pbds::rc_binomial_heap_tag>;
typedef long long lint;
#define INF (1LL<<60)
#define IINF (1<<30)
#define EPS (1e-10)
#define MOD 1000000007LL
//#define MOD 998244353LL
typedef vector<lint> vec;
typedef vector<vector<lint>> mat;
typedef vector<vector<vector<lint>>> mat3;
typedef vector<string> svec;
typedef vector<vector<string>> smat;
template<typename T>inline void numout(T t){bool f=0;for(auto i:t){cout<<(f?" ":"")<<i<INF/2?i:"INF";f=1;}cout<<endl;}
template<typename T>inline void numout2(T t){for(auto i:t)numout(i);}
template<typename T>inline void output(T t){bool f=0;for(auto i:t){cout<<(f?" ":"")<<i;f=1;}cout<<endl;}
template<typename T>inline void output2(T t){for(auto i:t)output(i);}
template<typename T>inline void _output(T t){bool f=0;for(lint i=0;i<t.size();i++){cout<<f?"":" "<<t[i];f=1;}cout<<endl;}
template<typename T>inline void _output2(T t){for(lint i=0;i<t.size();i++)output(t[i]);}
#define rep(i,n) for(lint i=0;i<lint(n);++i)
#define repi(i,a,b) for(lint i=lint(a);i<(lint)(b);++i)
#define rrep(i,n) for(lint i=lint(n)-1;i>=0;--i)
#define rrepi(i,a,b) for(lint i=lint(b)-1;i>=lint(a);--i)
#define irep(i) for(lint i=0;;++i)
#define all(n) begin(n),end(n)
#define dist(a,b,c,d) sqrt(pow(a-c,2)+pow(b-d,2))
inline lint gcd(lint A,lint B){return B?gcd(B,A%B):A;}
inline lint lcm(lint A,lint B){return A/gcd(A,B)*B;}
// inline cint cgcd(cint A,cint B){return B?cgcd(B,A%B):A;}
// inline cint clcm(cint A,cint B){return A/cgcd(A,B)*B;}
inline bool chmin(auto& s,const auto& t){bool res=s>t;s=min(s,t);return res;}
inline bool chmax(auto& s,const auto& t){bool res=s<t;s=max(s,t);return res;}
const vector<lint> dx={1,0,-1,0,1,1,-1,-1};
const vector<lint> dy={0,1,0,-1,1,-1,1,-1};
#define SUM(v) accumulate(all(v),0LL)
auto call=[&](auto f,auto... args){return f(f,args...);};


int main(){
    string s;
    cin>>s;
    cout<<s.substr(0,s.size()-8)<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int Maxn=500005,mod=998244353;
int fac[Maxn],ifac[Maxn];
int ksm(int x,int k){
    int ret=1,tmp=x;
    while(k){
        if(k&1)ret=1ll*ret*tmp%mod;
        tmp=1ll*tmp*tmp%mod;k>>=1;
    }
    return ret;
}
int inv(int x){return ksm(x,mod-2);}
int C(int n,int m){return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;}
int main(){
    for(int i=fac[0]=1;i<Maxn;i++)fac[i]=1ll*fac[i-1]*i%mod;
    for(int i=0;i<Maxn;i++)ifac[i]=inv(fac[i]);
    int n,m,ans=0;cin>>n>>m;
    for(int i=0,w=1;i<=min(n,m);i++,w*=-1)
        ans=(ans+1ll*w*C(n,i)*C(m,i)%mod*fac[i]%mod*ksm(m+1,n-i)%mod*ksm(n+1,m-i))%mod;
    cout<<(ans+mod)%mod<<"\n";
    return 0;
}

Measured memory_bytes: 4096
sx,sy,tx,ty = gets.split.map(&:to_i)
dy = ty - sy
dx = tx - sx
ans = ""
# path1
ans += "U"*dy
ans += "R"*dx
# path2
ans += "D"*dy
ans += "L"*dx
# path3
ans += "L"
ans += "U"*(dy+1)
ans += "R"*(dx+1)
ans += "D"
# path4
ans += "R"
ans += "D"*(dy+1)
ans += "L"*(dx+1)
ans += "U"
puts ans

Measured memory_bytes: 1916
#include<bits/stdc++.h>
using namespace std;
int main(){
    int i, n;
    long long ans=0;
    string str;
    map<string, int> mapa;
    scanf("%d", &n);
    for(i=0; i<n; i++){
        cin >> str;
        std::sort(str.begin(), str.end());
        mapa[str]++;
        if(mapa[str]>1){
            ans+=mapa[str]-1;
        }
    }
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 11136
def is_kawaisou(a, b, c):
    if a == b and a == c:
        return 'No'
    if a == b or b == c or a == c:
        return 'Yes'
    else:
        return 'No'


if __name__ == '__main__':
    a, b, c = map(int, input().split())
    print(is_kawaisou(a, b, c))


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

// 小数点以下桁数
// fixed << setprecision(i)

int64_t gcd(int64_t a,int64_t b){return (a%b==0?b:gcd(b, a%b));}
int64_t lcm(int a,int b){return (int64_t)a*b/gcd(a, b);}
int factorial(int a){int b=1;while(a){b*=a--;}return b;} //13以下対応
bool is_prime(int a){if(a<=1)return false;for(int i=2;(int64_t)i*i<=a;i++){if(a%i==0)return false;}return true;}
int get_adp(double x, int n){return (int)round((x-(int)x)*pow(10,n))%10;} // 小数点以下の指定桁の値を取得
int64_t sigma(int64_t s, int64_t n){return n*(2*s+n-1)/2;}

//順列の全列挙
// vector<int> v(N);
// iota(v.begin(), v.end(), 1);       // v に 1, 2, ... N を設定
// do {
//   for(auto x : v) cout << x << " "; cout << "\n";    // v の要素を表示
// } while( next_permutation(v.begin(), v.end()) ); 

//bit全探索
// for (int tmp = 0; tmp < (1 << ビット数); tmp++) {
//   bitset<ビット数> s(tmp);
//   // (ビット列sに対する処理)
// }

int main()
{
  int64_t a, b, c, d, cd_lcm, flag;

  cin >> a >> b >> c >> d;
  flag = a % c && a % d;
  cd_lcm = lcm(c, d);
  a -= (a / c) + (a / d) - (a / cd_lcm);
  a = max((int64_t)0, a);
  b -= (b / c) + (b / d) - (b / cd_lcm);
  b = max((int64_t)0, b);
  cout << max((int64_t)0, b - a) + flag << endl;
}


Measured memory_bytes: 3664
N, Q = gets.split.map(&:to_i)
G = Array.new(N + 1){[]}
(N - 1).times do
  a, b = gets.split.map(&:to_i)
  G[a] << b
  G[b] << a
end

cs = Array.new(N + 1, 0)
Q.times do
  p, x = gets.split.map(&:to_i)
  cs[p] += x
end
q = [1]
v = Array.new(N + 1, false)
while !q.empty?
  i = q.shift
  v[i] = true
  c = cs[i]
  G[i].each do |j|
    next if v[j]
    cs[j] += c
    q << j
  end
end
puts cs.drop(1).join(' ')

Measured memory_bytes: 27388
s = input()

for bit in range(1 << 3):
    ans = int(s[0])
    f = s[0]

    for i in range(3):
        if bit & (1 << i):
            ans += int(s[i + 1])
            f += "+"
        else:
            ans -= int(s[i + 1])
            f += "-"
        f += s[i + 1]

    if ans == 7:
        print(f + "=7")
        exit()

Measured memory_bytes: 3060
#include <stdio.h>
#include <algorithm>

int main(void){
    int a[3];

    scanf("%d%d%d", &a[0], &a[1], &a[2]);
    std::sort(a, a+3);

    printf("%d %d %d\n", a[0], a[1], a[2]);
    return 0;
}

Measured memory_bytes: 2740
N, M = map(int, input().split())
H = list(map(int, input().split()))
highest = [True for _ in range(N)]
for _ in range(M):
    a, b = map(lambda x: int(x) - 1, input().split())
    if H[a] == H[b]:
        highest[a] = False
        highest[b] = False
    elif H[a] > H[b]:
        highest[b] = False
    else:
        highest[a] = False
print(len([h for h in highest if h]))

Measured memory_bytes: 84948
#include<stdio.h>

void compare(int *a, int *b)
{
	int temp;
	if(*a > *b)
	{
		temp = *a;
		*a = *b;
		*b = temp;
	}
}

int main(){
	int a, b, c, n, i;
	
	scanf("%d", &n);
	for(i = 0; i < n; i++)
	{
		scanf("%d %d %d", &a, &b, &c);
		
		compare(&a, &b);
		compare(&b, &c);
		
		if(a*a + b*b == c*c)
		{
			puts("YES");
		}
		else
		{
			puts("NO");
		}
		
	}
	
    return 0;
}

Measured memory_bytes: 576
#include <bits/stdc++.h>
#define err(args...) {}
#ifdef DEBUG
#include "_debug.cpp"
#endif
using namespace std;
using ll = long long;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    string s;
    cin >> s;
    string sub = s.substr(2);
    sub.pop_back();
    vector<int> a;
    for(int i = 0; i < s.size(); i++) {
        if('A' <= s[i] and s[i] <= 'Z') {
            a.push_back(i);
        }
    }
    if(s[0] == 'A' and find(sub.begin(), sub.end(), 'C') != sub.end()
        and a == vector<int>{0, 2 + (find(sub.begin(), sub.end(), 'C') - sub.begin())}) {
        cout << "AC" << endl;
    } else {
        cout << "WA" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(){
  int n,a[101],b[101],i,ans=0;
  scanf("%d",&n);
  for(i=0; i<n-1; i++){
    scanf("%d",&b[i]);
  }
  a[0]=b[0];
  for(i=0; i<n-2; i++){
    for(int j=i+1; j<n; j++){
      if(b[i]>b[j]){
        a[j]=b[j];
      }
      else{
        a[j]=b[i];
      }
    }
  }
  a[n-1]=b[n-2];
  for(i=0; i<n; i++){
    ans+=a[i];
  }
  printf("%d\n",ans);
  return 0;
}


Measured memory_bytes: 128
fun main(args: Array<String>) {
    var N = readLine()!!.toInt()
    var S = readLine()!!.toString()
    var max = 0
    var x = 0
    (0..N-1).map{i->
        if (S[i] == 'I')x++
        else x--
        
        if(max<x) max = x
    }
    println(max)
   
}


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

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define fst first
#define snd second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define EPS (1e-9)
#define equals(a,b) (fabs((a)-(b))<EPS)

using namespace std;

bool LT(double a,double b) { return !equals(a,b) && a < b; }
bool LTE(double a,double b) { return equals(a,b) || a < b; }

const string YES = "";
const string NO  = "";

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

map<ll,int> prime_factor(ll n) {
  map<ll,int> res;
  for(ll i=2;i*i<=n;i++) {
    while(n % i == 0) {
      ++res[i];
      n /= i;
    }
  }
  if(n != 1)res[n] = 1;
  return res;
}


void solve() {

}

int dp[64];

int main() {
  memset(dp,-1,sizeof dp);
  dp[0] = 0;
  REP(i,1,64) {
    for(int j=63;j>=0;--j) {
      if( dp[j] == -1 ) continue;
      if( j + i < 64 ) {
	dp[j+i] = max(dp[j+i],dp[j]+1);
      }
    }
  }
  //rep(i,10) {
  //cout << i << " : " << dp[i] << endl;
  //}
  
  ll n;
  cin >> n;
  map<ll,int> pf = prime_factor(n);
  ll ans = 0;
  for(auto v : pf) {
    //cout << v.fst << " : " << v.snd << endl;
    if( v.fst >= 2LL ) {
      assert( v.snd < 64 );
      ans += dp[v.snd];
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3632
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <array>
#include <algorithm>
#include <set>
#include <iomanip>
#include <cstdio>

using namespace std;

#define int long long

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

    int a, s;
    cin >> a >> s;

    if (a < s)
    {
        cout << 0 << endl;
    }
    else
    {
        cout << 10 << endl;
    }

}

Measured memory_bytes: 256
const input = require('fs').readFileSync('/dev/stdin', 'utf8').split(/\n/);
const even = '#' + '.';
const odd = '.' + '#';
for (let i = 0; i < input.length; i++) {
    let [a, b] = input[i].split(' ').map(Number);
         if (a === 0 && b === 0) {
        break;
         }
    for (let j = 0; j < a; j++) {
        if (j % 2 === 0) {
        console.log(even.repeat(b).slice(0, b));
        } else {
        console.log(odd.repeat(b).slice(0, b));
        }
    }
    console.log("");
}


Measured memory_bytes: 18568
#include<stdio.h>
#include<stdlib.h>

int min(int num1,int num2,int num3){
    if(num1 <= num2 && num1 <= num3){
        return num1;
    }else if(num2 <= num1 && num2 <= num3){
        return num2;
    }else{
        return num3;
    }
}

int main(void){

    int N,X,Y,ans[2001],i,j,tmp;

    scanf("%d %d %d",&N,&X,&Y);
    for(i = 0;i < N;i++){
        ans[i] = 0;
    }

    for(i = 0;i < N;i++){
        for(j = i+1;j < N;j++){
           tmp = min(abs(j - i),abs((X-1) - i)+1+abs(j - (Y-1)),abs((Y-1) - i)+1+abs(j - (X-1)));
           ans[tmp]++;
        }
    }

    for(i = 1;i <= N-1;i++){
        printf("%d\n",ans[i]);
    }

    return 0;
}


Measured memory_bytes: 128
#include <cstdio>
#include <vector>
#include <complex>
#include <cmath>
using namespace std;

#define EPS 1e-7

typedef complex<double> P;
typedef const P &rP;
typedef const vector<P> &cvP;

double pi;

bool checkarg(double a, double b, double c){
	double pi2 = pi * 2.0;
	while(b + EPS < a) b += pi2;
	while(b > a + pi2 + EPS) b -= pi2;
	while(c + EPS < b) c += pi2;
	while(c > a + pi2 + EPS) c -= pi2;

	return a < b + EPS && b < c + EPS;
}

vector<P> input(int n){
	int x, y;
	vector<P> v(n);
	for(int i = 0; i < n; ++i){
		scanf("%d%d", &x, &y);
		v[i] = P(x, y);
	}
	return v;
}

bool reach(P house, double d, double a, double w){
	if(norm(house) > a * a + EPS) return false;
	return checkarg(w - d * 0.5, arg(house), w + d * 0.5);
}

bool check(rP house, cvP us, double du, cvP ms, double dm, cvP ss, double ds, double a, double w){
	if(!reach(house, du, a, w)) return false;
	for(int i = 0; i < us.size(); ++i){
		if(reach(house - us[i], du, a, w)) return false;
	}
	for(int i = 0; i < ms.size(); ++i){
		if(reach(house - ms[i], dm, a, w)) return false;
	}
	for(int i = 0; i < ss.size(); ++i){
		if(reach(house - ss[i], ds, a, w)) return false;
	}
	return true;
}

int main(){
	pi = acos(-1.0);

	int h, r, u, m, s;
	double du, dm, ds;
	while(scanf("%d%d", &h, &r), h){
		vector<int> ans;
		int mincnt = 1;
		
		vector<P> hs = input(h);

		scanf("%d%d%d%lf%lf%lf", &u, &m, &s, &du, &dm, &ds);
		du *= pi / 180.0;
		dm *= pi / 180.0;
		ds *= pi / 180.0;

		vector<P> us = input(u), ms = input(m), ss = input(s);

		vector<double> w(r), a(r);
		for(int i = 0; i < r; ++i){
			scanf("%lf%lf", &w[i], &a[i]);
			w[i] *= pi / 180.0;
		}

		for(int i = 0; i < h; ++i){
			int cnt = 0;
			for(int j = 0; j < r; ++j){
				if(check(hs[i], us, du, ms, dm, ss, ds, a[j], w[j])){
					++cnt;
				}
			}

			if(cnt > mincnt){
				mincnt = cnt;
				ans.clear();
			}
			if(cnt == mincnt){
				ans.push_back(i + 1);
			}
		}
		
		if(ans.empty()){
			puts("NA");
		}
		else{
			printf("%d", ans[0]);
			for(int i = 1; i < ans.size(); ++i){
				printf(" %d", ans[i]);
			}
			puts("");
		}
	}
}

Measured memory_bytes: 1168
# -*- coding: utf-8 -*-
import bisect
import sys

sys.setrecursionlimit(1000000)
input = sys.stdin.buffer.readline
INF = 2**62-1


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


ans = [-1] * (2*10**5+1)


@mt
def slv(N, A, UV):
    A.insert(0, -1)
    g = [list() for _ in range(0, N+1)]
    for u, v in UV:
        g[u].append(v)
        g[v].append(u)

    def dfs(u, p, dp):
        global ans

        for v in g[u]:
            if v == p:
                continue

            i = bisect.bisect_left(dp, A[v])
            b = dp[i]
            dp[i] = A[v]
            ans[v] = bisect.bisect_left(dp, INF)
            dfs(v, u, dp)
            dp[i] = b
    dp = [INF] * (N+1)
    dp[0] = A[1]
    dfs(1, 0, dp)

    ans[1] = 1
    for i in range(1, N+1):
        print(ans[i])


def main():
    N = read_int()
    A = read_int_n()
    UV = [read_int_n() for _ in range(N-1)]
    slv(N, A, UV)


if __name__ == '__main__':
    main()


Measured memory_bytes: 307244
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a,b[100],e,ans=0;
  string c[100],d;
  cin>>a;
  for(int i=0;i<a;i++){
    cin>>c[i]>>b[i];
  }
  cin>>d;
  for(int i=0;i<a;i++)
    if(d==c[i])
      e=i;
  for(int i=e+1;i<a;i++)
    ans+=b[i];
  cout<<ans<<endl;
    
  return(0);
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;
using ll=long long;
#define rep(i,a,b) for(ll i=a;i<ll(b);i++)
#define repr(i,a,b) for(ll i=a;i>=ll(b);i--)
#define endl "\n"
#define ALL(x) x.begin(),x.end()
#define ALLR(x) x.rbegin(),x.rend()
#define INF 1e9
#define DEBUG(x) cout<<"debug: "<<x<<endl

int n;
int main() {
    cin >> n;
    vector<int> a(n);
    rep(i, 0, n) cin >> a[i];

    int wx = a[0];
    rep(i, 1, n) wx ^= a[i];

    rep(i, 0, n){
        int out = wx ^ a[i];
        cout << out;
        if(i != n-1) cout << " ";
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 3644
N = int(input())
S = input()
first_check = [0] * 10
ans = 0
for i in range(N):
    if first_check[int(S[i])] == 1:
        continue
    second_check = [0] * 10
    for k in range(i+1,N):
        if second_check[int(S[k])] == 1:
            continue
        ans += len(set(list(S[k+1:])))
        second_check[int(S[k])] = 1
    first_check[int(S[i])] = 1
print(ans)

Measured memory_bytes: 3344
#pragma comment(linker,"/stack:16777216")
#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<list>
#include<stack>
#include<queue>
#include<deque>
#include<functional>
#include<utility>
#include<algorithm>
#include<sstream>
#include<cstring>
#include<cmath>
#include<cctype>
#include<exception>
#include<climits>
#include<cfloat>
#include<iomanip>
#include<bitset>
#include<streambuf>
#include<cstdlib>
#include<ctime>
//#include"functions.h"
//#include"highprecision.h"
#define pb push_back
#define pf push_front
#define ppb pop_back
#define mp make_pair
#define np next_permutation
#define fi first
#define sc second
#define vi vector<int>
#define vll vector<long long>
#define vvi vector<vector<int> >
#define vpi vector<pair<int,int> >
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pff pair<float,float>
#define pdd pair<double,double>
#define psi pair<string,int>
#define pis pair<int,string>
#define ppi pair<pii,int>
#define pdi pair<pii,pii>
#define LN 84757
#define INF 1e9
#define LLINF 1e18
#define MAXINT 0x7fffffff
#define MAXLL 0x7fffffffffffffff
#define EPS 1e-5
#define DEPS 1e-9
#define LDEPS 1e-13
#define MOD 1000000007
#define E 2.7182818284
#define PI 3.1415926535
#define rep(a,b) for(int a=0;a<b;a++)
#define rep(a,b) for(int a=0;a<b;a++)
#define forn(a,n) for(int a=1;a<=n;a++)
#define forr(a,n) for(int a=n;a>=1;a--)
#define repn(a,n,p) for(int a=0;a<n;a+=p)
#define repr(a,n) for(int a=n-1;a>=0;a--)
#define foreach(a,b) for(__typeof(b.begin())a=b.begin();a!=b.end();a++)
#define fillemp(a) memset(a,0,sizeof(a))
#define fillinf(a) memset(a,0x3f,sizeof(a))
#define frestream freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define stdf(a,b) freopen(a,"r",stdin);freopen(b,"w",stdout);
#define inputf(a) freopen(a,"r",stdin);
#define outputf(a) freopen(a,"w",stdout);
#define sz(a) a.size()
#define all(a) a.begin(),a.end()
#define MOD 1000000007
typedef long long ll;
typedef long double ld;
using namespace std;

int a[10];
int main(int argc,char** argv){
	int n,m;
	cin>>n>>m;
	rep(i,10){
		a[i]=-1;
	}
	if(n==1&&m==0){
		cout<<0;
		return 0;
	}
	rep(i,m){
		int s,c;
		cin>>s>>c;
		s--;
		if(n!=1&&s==0&&c==0){
			cout<<-1;
			return 0;
		}
		if(a[s]!=-1&&a[s]!=c){
			cout<<-1;
			return 0;
		}
		a[s]=c;
	}
	if(a[0]==-1)a[0]=1;
	for(int i=1;i<n;i++){
		if(a[i]==-1){
			a[i]=0;
		}
	}
	rep(i,n){
		cout<<a[i];
	}
	return 0;
}

Measured memory_bytes: 256
#include<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_set>
#include<unordered_map>
#include<fstream>
#include<list>
#include<functional>
#include<bitset>
#include<complex>
#include<tuple>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<double,ll> pdl;
#define F first
#define S second
const ll E=1e18+7;
const ll MOD=998244353;

ll n;
vector<bool> x;
vector<bool> a,b;

void mns(){
    for(ll i=(int)a.size()-1;i>=(int)b.size()-1;i--){
        if(a[i]==1){
            for(int t=0;t<b.size();t++){
                a[i-t]=a[i-t]^b[b.size()-t-1];
            }
        }
    }
    while(!a.empty() && a.back()==0){a.pop_back();}
    swap(a,b);
}








int main(){
    vector<ll> P(1000000,1);
    for(ll i=1;i<P.size();i++){P[i]=P[i-1]*2%MOD;}
    cin>>n;
    string X;
    cin>>X;
    reverse(X.begin(),X.end());
    x.resize(X.size());
    for(int i=0;i<X.size();i++){
        x[i]=X[i]-'0';
    }
    string A;
    cin>>A;
    reverse(A.begin(),A.end());
    a.resize(A.size());
    for(int i=0;i<A.size();i++){
        a[i]=A[i]-'0';
    }
    for(int i=1;i<n;i++){
        string B;
        cin>>B;
        reverse(B.begin(),B.end());
        b.resize(B.size());
        for(int i=0;i<B.size();i++){
            b[i]=B[i]-'0';
        }
        if(a.size()<b.size()){swap(a,b);}
        while(b.size()){mns();}
    }
    ll ans=0;
    vector<bool> Z(x.size(),false);
    for(ll i=(int)x.size()-1;i>=(int)a.size()-1;i--){
        if(x[i]){
            ans+=P[i-(a.size()-1)];
            ans%=MOD;
            if(Z[i]==0){
                for(int t=0;t<a.size();t++){
                    Z[i-t]=Z[i-t]^a[a.size()-1-t];
                }
            }
        }
        else{
            if(Z[i]){
                for(int t=0;t<a.size();t++){
                    Z[i-t]=Z[i-t]^a[a.size()-1-t];
                }
            }
        }
    }
    bool j=true;
    for(ll i=x.size()-1;i>=0;i--){
        if(x[i]==false && Z[i]==true){j=false;}
        if(x[i]==true && Z[i]==false){break;}
    }
    if(j){ans++;}
    cout<<ans%MOD<<endl;
    
    
    return 0;
}


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

int findSumOfDigits(int n){
    int sum = 0;
    while(n > 0){
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

int main(){
    int N, A, B;
    cin >> N >> A >> B;
    int total = 0;
    for(int i=1; i<=N; i++){
        int sum = findSumOfDigits(i);
        if(sum >= A && sum <= B){
            total += i;
        }
    }

    cout << total << endl;
}

Measured memory_bytes: 256
[N, M, X] = map(int, list(input().split(' ')))
A = []
C = []
for i in range(N):
    c, *a = map(int, input().split(' '))
    C.append(c)
    A.append(a)
#print(C)
#print(A)

INF = 10**10
min_cost = INF

for b in range(2**N): 
    # これがバイナリーベースの全探索となる。今回のキモ part 1
    # 一つのループが本の購入セットに対応している
    # 各ビットがそれぞれの本を購入するかどうか表している
    # 因みに b は bit を表しているつもり
    cost = 0 # この購入セットで使う金額
    algo_level = [0] * M # 各アルゴリズムトピックの理解度
    for i in range(N): 
        # これが各本のコストと理解度取得のためのループ
        # i 番目の本に対してループを回していく
        if(b >> i & 1): # この行が今回のキモ part 2。
            # i 番目の本の購入有無を判定するために、ビットシフトした値に対して '1 = 0b1' (つまり単なる (2進数の) 1) との論理積を求めている
            # この if 文が True であるということは、i 番目の本を買ったということ
            cost += C[i]
            for a in range(M): # (各本にある) 各アルゴリズムに対するループ
                algo_level[a] += A[i][a]
    if(min(algo_level) >= X): # 全てのアルゴリズムトピックが X 以上の理解度である場合…
        min_cost = min(cost, min_cost)

if(min_cost < INF):
    print(min_cost)
else:
    print('-1')






Measured memory_bytes: 9156
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    R, G, B, n = map(int, input().split())

    res = 0
    for r in range(n // R + 1):
        for g in range(n // G + 1):
            b = (n - (R * r + G * g)) // B
            if R * r + G * g + B * b == n and b >= 0:
                res += 1

    print(res)


if __name__ == '__main__':
    resolve()


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

#define all(x) (x).begin(), (x).end()
#define inf (sizeof(int) == 4 ? (int)1E9 : (int)1E18)

template<class T> istream& operator>>(istream& I, vector<T>& v) {for (T &e: v) I >> e; return I;}


void _main() {
        int n; cin >> n;
        n %= 10;
        if (n == 2 || n == 4 || n == 5 || n == 7 || n == 9) cout << "hon";
        else if (n == 0 || n == 1 || n == 6 || n == 8) cout << "pon";
        else cout << "bon";
}



signed main() {
        ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
        int _t = 1;
//        cin >> _t;
        while (_t--) _main();
        return 0;
}

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

int N;

int main() {
    cin >> N;
    vector<int> P(N);
    vector<int> Q(N);
    for (int i = 0; i < N; i++) cin >> P[i];
    for (int i = 0; i < N; i++) cin >> Q[i];

    vector<int> v(N);
    iota(v.begin(), v.end(), 1);
    
    int cnt = 0;
    int a = 0;
    int b = 0;
    do {
        cnt++;
        bool fp = true;
        bool fq = true;
        for (int i = 0; i < N; i++) {
            if (P[i] != v[i]) fp = false;
            if (Q[i] != v[i]) fq = false;
        }

        if (fp) a = cnt;
        if (fq) b = cnt;
    } while(next_permutation(v.begin(), v.end()));    

    cout << abs(a - b) << endl; 

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
 
int main(){
  int N,M,C; 
  cin >> N >> M >> C;
  int B[20];
  for(int i=0;i<M;i++){
    cin >> B[i];
  }
  int A[20][20];
  for(int i=0;i<N;i++){
    for(int j=0;j<M;j++){
      cin >> A[i][j];
    }
  }
  int ans=0;
  for(int i=0;i<N;i++){
      int sum=0;
    for(int j=0;j<M;j++){
      sum+=A[i][j]*B[j];   
    }
    if(sum+C>0){ans++;}
  }
   cout << ans << endl;
  return 0;
}

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

int main() {
  int N; cin >> N;
  long long tmp, ans=0, minabs=1e9, mincnt=0;
  for (int i=0; i<N; i++) {
    cin >> tmp;
    ans+=abs(tmp);
    minabs = min(minabs, abs(tmp));
    if (tmp<0) mincnt++;
  }
  if(mincnt%2==0) cout << ans << "\n";
  else cout << ans-2*minabs << "\n";
}

Measured memory_bytes: 256
/*
 * Copyright (c) 2019 ... All rights reserved.
 * ...
 */
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>

#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
typedef long long ll;

using namespace std;


int inputValue(){
    int a;
    cin >> a;
    return a;
};

void inputArray(int * p, int a){
    rep(i, a){
        cin >> p[i];
    }
};

void inputVector(vector<int> * p, int a){
    rep(i, a){
        int input;
        cin >> input;
        p -> push_back(input);
    }
}

template <typename T>
void output(T a, int precision) {
    if(precision > 0){
        cout << setprecision(precision)  << a << "\n";
    }
    else{
        cout << a << "\n";
    }
}

int main(int argc, const char * argv[]) {

    // source code
    int K = inputValue();
    int S = inputValue();

    int x, y, z;

    int counter = 0;
    rep(i, K+1){
        rep(j, K+1){
            if(S - i - j >= 0 and S - i - j <= K){
                counter++;
            }
        }
    }

    cout << counter << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,m,n) for(int i=m;i<n;i++)
ll mod=1e9+7;

int main(){
  int a,b,c;
  cin>>a>>b>>c;
  int d=max(a,max(b,c));
  if(d==a+b+c-d) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using vec=vector<ll>;
using mat=vector<vec>;
#define For(i,a,b) for(i=a;i<b;i++)
#define rep(i,N) For(i,0,N)
#define rep1(i,N) For(i,1,N)
#define all(v) (v).begin(),(v).end()
#define allr(v) (v).rbegin(),(v).rend()
#define vsort(v) sort(all(v))
#define vrsort(v) sort(allr(v))
#define mod 1000000007
using datas=pair<ll,ll>;

long mmid(long a,long b,long c){return a<b?(b<c?b:max(a,c)):(b>c?b:min(a,c));}

ll modinv(ll a) {
  ll b=mod,u=1,v=0,t;
  while(b){
    t=a/b;
    a-=t*b; swap(a,b);
    u-=t*v; swap(u,v);
  }
  return (u+mod)%mod;
}

ll moddevide(ll a,ll b){return (a*modinv(b))%mod;}

ll modncr(ll n,ll r){
  ll i,plus=1;
  rep(i,r){
    plus=(plus*(n-i))%mod;
    plus=moddevide(plus,i+1);
  }
  return plus;
}

ll euclidean_gcd(ll a, ll b) {
  if(a<b) return euclidean_gcd(b, a);
  ll r;
  while ((r=a%b)){a=b;b=r;}
  return b;
}

ll countdigits(ll n){
  ll ans=0;
  while(n){n/=10;ans++;}
  return ans;
}

ll sumdigits(ll n){
  ll ans=0;
  while(n){ans+=n%10;n/=10;}
  return ans;
}

void printmap(vector<ll>& a,ll H,ll W){
  ll i,j;
  For(i,0,H+2){
    For(j,0,W+2){cout<<a[i*(W+2)+j];}
    cout<<endl;
  }
}
void inputmap(vector<ll>& a,ll H,ll W){
  ll i,j;
  string ss;
  For(i,1,H+1){
    cin>>ss;
    For(j,1,W+1){
      if(ss[j-1]=='#'){
        a[i*(W+2)+j]=1;
      }else{
        a[i*(W+2)+j]=0;
      }
    }
  }
}

void dijkstra(vector<vector<datas>>& tree,vector<ll>& d,ll start){
  ll i,K=tree[start].size(),N=d.size(),cnt=1;
  datas x;
  d[start]=0;
  priority_queue<datas,vector<datas>,greater<datas>> que;
  rep(i,K){
    que.push(datas(tree[start][i].second,tree[start][i].first));
  }
  while(cnt<N){
    x=que.top();que.pop();
    if(d[x.second]>0)continue;
    d[x.second]=x.first;
    cnt++;
    K=tree[x.second].size();
    rep(i,K){
      if(d[tree[x.second][i].first]<0){
        que.push(datas(d[x.second]+tree[x.second][i].second,tree[x.second][i].first));
      }
    }
  }
}


int main(){
  ll i,N,f=1;
  vector<ll> v(3,0);
  string ss;
  cin>>ss;
  N=ss.size();
  rep(i,N){
    v[ss[i]-'a']++;
  }
  vsort(v);
  if(v[0]==0&&v[2]>1)f=0;
  if(v[2]-v[0]>1){
    f=0;
  }
  if(f){
    cout<<"YES"<<endl;
  }else{
    cout<<"NO"<<endl;
  }
  return 0;
}

Measured memory_bytes: 512
data = STDIN.read.strip.split("\n")
if data[0] == data[1]
  puts "Yes"
  exit
end
if data.map { |d| d.chars.sort.join }.uniq.size != 1
  puts "No"
  exit
end
data[0].size.times do |i|
  len = data[0].size - 1
  dd = data[0] + data[0]
  if dd.chars[i..i + len].join == data[1]
    puts "Yes"
    exit
  end
end
puts "No"

Measured memory_bytes: 2172
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep_lr(i,l,r) for(int i=(l);i<(r);i++)
#define all(x) (x).begin(),(x).end()
#define V vector
typedef V<int> vi;
typedef V<vi> vvi;
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<int, int, int> T;
constexpr int INF = INT_MAX >> 1;
constexpr ll LINF = 5000000000000000LL;
constexpr int MOD = 1000000007;

int main() {

	int x;
	cin >> x;
	int k = 0;
	while (true) {
		k++;
		if (k * x % 360)continue;
		cout << k << endl;
		return 0;
	}
}

Measured memory_bytes: 3632
#include <iostream>
using namespace std;
int main()
{
  int w,h,x,y,r;
  cin>>w>>h>>x>>y>>r;
  if((r<=x)&&(x<=w-r)&&(r<=y)&&(y<=h-r))
    cout<<"Yes"<<endl;
  else
    cout<<"No"<<endl;

}

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

int main()
{
    int n,i;
    cin >> n;
    vector<int> d(n);
    for(i = 0;i < n;++i){
        cin >> d.at(i);
    }
    sort(d.begin(),d.end());
    cout << d.at(n/2)-d.at(n/2-1) << endl;
    return 0;
}

Measured memory_bytes: 640
n = int(input())
a = [int(input()) for i in range(n)]
a.sort()

i = 0 ; j = n-1; last = j;
ret = ret2 = 0
diff = 10**9

while i != j:
    last = j
    ret += a[j] - a[i]
    diff = min(diff, a[j] - a[i])
    
    i+=1
    if i==j: break
    last = i
    ret += a[j] - a[i]
    diff = min(diff, a[j] - a[i])

    j-=1
ret += a[last] - a[0]
diff = min(diff, a[last] - a[0])
ret -= diff

i = 0 ; j = n-1; last = j;

while i != j:
    last = i
    ret2 += a[j] - a[i]
    diff = min(diff, a[j] - a[i])
    
    j-=1
    if i==j: break
    last = j
    ret2 += a[j] - a[i]
    diff = min(diff, a[j] - a[i])

    i+=1
ret2 += a[n-1] - a[last]
diff = min(diff, a[n-1] - a[last])
ret2 -= diff

print(max(ret,ret2))


Measured memory_bytes: 7512
import java.util.*;
public class Main {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
                Scanner sc = new Scanner(System.in);
                int N = sc.nextInt();
		double P = 1;
		for(int i=1;i<=N;i++){
			P = (P*i)%(Math.pow(10.0,9.0) + 7.0);
		}
	        System.out.println((int)P);
	}

}

Measured memory_bytes: 23508
#include<bits/stdc++.h>
#define mo 1000000007
#define ny 499122177
#define maxn 1000000000000000000LL
#define pi 3.1415926535898
#define eps 1e-9 
using namespace std;
long long read(){
    long long xx=0,flagg=1; 
    char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')
        ch=getchar();
    if(ch=='-'){
        flagg=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        xx=xx*10+ch-'0';
        ch=getchar();
    }
    return xx*flagg;
}
void pus(long long xx,long long flagg){
    if(xx<0){
        putchar('-');
        xx=-xx;
    }
    if(xx>=10)
        pus(xx/10,0);
    putchar(xx%10+'0');
    if(flagg==1)
        putchar(' ');
    if(flagg==2)
        putchar('\n');
    return;
}
long long n,s,i,x[100005],p[100005],l,r,flag,flag2,sum;
int main(){
//	freopen("number.in","r",stdin);
//	freopen("number.out","w",stdout);
	n=read();s=read();
	for(i=1;i<=n;i++){
		x[i]=read();
		p[i]=read();
		if(x[i]<s)
			flag=i;
	}
	l=1;r=n;
	while(l<=flag&&r>=flag+1){
		if(p[l]<p[r]){
			if(flag2!=1)
				sum+=x[r]-x[l];
			p[r]+=p[l];
			l++;
			flag2=1;
		}
		else{
			if(flag2!=2)
				sum+=x[r]-x[l];
			p[l]+=p[r];
			r--;
			flag2=2;
		}
	}
	if(r<=flag)
		sum+=s-x[l];
	else
		sum+=x[r]-s;
	pus(sum,2);
  	return 0;
}

Measured memory_bytes: 1792
/*Function Template*/
#include<bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
#define rep(i, n) for(long long int i = 0; i < (n); i++)


int Len(int n) {
  int s=0;
  while(n!=0) s++, n/=10;
  return s;
}


int Sint(int n) {
  int m=0,s=0,a=n;
  while(a!=0) s++, a/=10;
  for(int i=s-1;i>=0;i--) m+=n/((int)pow(10,i))-(n/((int)pow(10,i+1)))*10;
  return m;
}


int Svec(vector<int> v){
  int n=0;
  for(int i=0;i<v.size();i++) n+=v[i];
  return n;
}


int GCD(int a,int b){
  int r,tmp;
/*自然数 a > b を確認・入替*/
  if(a<b){
    tmp=a,a=b,b=tmp;
  }
/*ユークリッドの互除法*/
  r=a%b;
  while(r!=0){
    a=b,b=r,r=a%b;
  }
  return b;
}


int LCM(int a,int b){
  int c=a,d=b,r,tmp;
/*自然数 a > b を確認・入替*/
  if(a<b){
    tmp=a,a=b,b=tmp;
  }
/*ユークリッドの互除法*/
  r=a%b;
  while(r!=0){
    a=b,b=r,r=a%b;
  }
  return c/b*d;
}


int Factorial(int n){
  int m=1;
  while(n>=1) m*=n,n--;
  return m;
}


/*↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓*/
int main() {
  double n;
  cin>>n;
  vector<int> v(n);
  rep(i,n) cin>>v[i];
  double a=(double)Svec(v)/n;
  double ans=1000000000;
  int cnt=0;
  rep(i,n){
    if(abs(a-v[i])<ans){
      ans=(double)abs(a-v[i]);
      cnt=i;
    }
  }
  cout<<cnt<<endl;

}




Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
int gcd(int a, int b) {
	if (!b)return a;
	return gcd(b, a%b);
}
int main(){
	int n,X,x,ans;cin>>n>>X;
	cin>>x;ans=abs(x-X);
	for (int i=1;i<n;++i){
		cin>>x;ans=gcd(abs(x-X),ans);
	}cout<<ans;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define int long long int
int dp[3005][3005];
const int N=998244353;
main() {
	int n, s;
	cin>>n>>s;
	int arr[n];
	for(int i=0; i<n; i++){
		cin>>arr[i];
	}
	dp[0][0]=2;
	dp[0][arr[0]]=1;
	for(int i=1; i<n; i++){
		for(int j=0; j<=3000; j++){
			dp[i][j]=(dp[i][j]+(2*dp[i-1][j]))%N;
			if(arr[i]+j>3000){
				continue;
			}
			dp[i][j+arr[i]]=(dp[i][j+arr[i]]+dp[i-1][j])%N;
		}
	}
	cout<<dp[n-1][s];
	return 0;
}

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

#define rep(i,n) for(int i=0;i<n;i++)
#define srep(i,s,e) for(int i=s;i<=e;i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define MAX (int)1e9 + 99
#define maxof(a,b,c) max(a,max(b,c))
#define minof(a,b,c) min(a,min(b,c))
#define vi vector<int>
#define vvi vector<vector<int>>
#define vb vector<bool>
#define ll long long
#define ull unsigned long long
#define vll vector<ll>
#define pa pair<int, int>
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define bitcnt(x) __builtin_popcount(x)
#define gcd(a,b) __gcd(a,b)
#define all(x) (x).begin(),(x).end()
#define ts(x) to_string(x)
#define rsort(a) sort(all(a)); reverse(all(a))
#define set0(x) memset(x, 0, sizeof(x))
const double pi = 3.14159265358979323846;
ll binpow(ll, ll);
ll mult(ll, ll);
ll add(ll , ll);
ll division(ll, ll);
ll nCr(ll, ll);
ll inv(ll);
void calc();
void maxi(int &a, int b) {if(a<b) a = b;}
void mini(int &a, int b) {if(a>b) a = b;}
template<class T> istream &operator>>(istream &is, vector<T> &v) { for (T &x : v) is >> x; return is;}
template<class T> ostream &operator<<(ostream &os, const vector<T> &v) {if (!v.empty()) {os << v.front();for (int i = 1; i < v.size(); ++i) os << ' ' << v[i];} return os;}
const int N=1e6+5;
const int MOD = 1e9+7;
// ll fact[N];


void solve()
{
    ll n;
    cin>>n;
    if(n==1) cout<<0;
    else if(n==2) cout<<2;
    else {
        ll ans = binpow(10, n);
        ans = add(ans, -2*(binpow(9,n)));
        ans = add(ans, binpow(8, n)); 
        cout<<ans;
    }
}

int main()
{
    fastio;
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    int t=1;
    // cin>>t;
    
    rep(i,t)
    {
        solve();
        cout<<"\n";
    }
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
    return 0;
}








ll add(ll a, ll b){
    a+=b;
    while(a>=MOD) a-=MOD;
    while(a<0) a+=MOD;
    return a;
}

ll mult(ll a, ll b){
    return (a * 1ll * b) % MOD;
}


ll binpow(ll a, ll b){
    ll c = 1;
    while(b > 0)
    {
        if(b % 2 == 1)
            c = mult(c, a);
        a = mult(a, a);
        b /= 2;
    }
    return c;   
}

ll inv(ll a){
    return binpow(a, MOD-2);
}

ll division(ll a, ll b){
    return mult(a, inv(b));
}

// ll nCr(ll n, ll r){
//     if(r > n) return 0;
//     return division(fact[n], mult(fact[n-r], fact[r]));
// }

// void calc(){
//     fact[0] = 1;
//     srep(i,1,N-1)
//         fact[i] = (i*1ll*fact[i-1])%MOD;

// }

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

const long long INF = 1LL << 60;

int main(){
    int N, K;
    cin >> N >> K;
    vector<int> h(N + 100);
    for(int i = 0; i < N; i++){
        cin >> h.at(i);
    }
    
    long long dp[110000];

    for(int i = 0; i < 110000; i++) dp[i] = INF;

    dp[0] = 0;

    for(int i = 0; i < N; i++){
        for(int k = 1; k <= K; k++){
            if(dp[i + k] > dp[i] + abs(h.at(i) - h.at(i + k))){
                dp[i + k] = dp[i] + abs(h.at(i) - h.at(i + k));
            }
        }
    }

    cout << dp[N - 1] << endl;
}

Measured memory_bytes: 1536