akhauriyash/Code-Regression huggingface dataset:
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		//		new Main().solveA();
		//		new Main().solveB();
		new Main().solveC();
		// new Main().solveD();
	}

	private void solveA() {
		Scanner scanner = null;
		int numN = 0;

		try {
			scanner = new Scanner(System.in);
			numN = scanner.nextInt();

			if (numN % 2 == 0) {
				System.out.println(numN);
			} else {
				System.out.println(numN * 2);
			}

			System.out.println("");

		} finally {
			if (scanner != null) {
				scanner.close();
			}
		}
	}

	private void solveB() {
		Scanner scanner = null;
		int numN = 0;

		try {
			scanner = new Scanner(System.in);
			numN = scanner.nextInt();
			int[] wk = new int[numN];

			for (int i = 0; i < wk.length; i++) {
				wk[i] = scanner.nextInt();
			}
			Arrays.sort(wk);

			System.out.println(wk[wk.length - 1] - wk[0]);

			System.out.println("");

		} finally {
			if (scanner != null) {
				scanner.close();
			}
		}
	}

	private int getCry(int b, int currentI, int maxI, int[] wk) {
		if (currentI == maxI) {
			return 0;
		}

		return getCry(b, currentI + 1, maxI, wk) + Math.abs(wk[currentI] - (b + currentI + 1));
	}

	/**
	 * ⅰ)abs(xi-a)の総和(aとの距離の総和)を最小にするのは中央値で、
	 * ⅱ)(xi-a)^2の総和を最小にするのは平均値
	 */
	private void solveC() {
		Scanner scanner = null;
		int numN = 0;

		try {
			scanner = new Scanner(System.in);
			numN = scanner.nextInt();
			int[] wk = new int[numN];

			for (int i = 0; i < wk.length; i++) {
				wk[i] = scanner.nextInt();
			}

			int[] wkWk = new int[numN];
			for (int i = 0; i < numN; i++) {
				wkWk[i] = wk[i] - (i + 1);
			}
			Arrays.sort(wkWk);

			int b = 0;
			if (numN % 2 == 0) {
				b = wkWk[numN / 2 - 1];
			} else {
				b = wkWk[numN / 2];
			}

			long res = 0;

			for (int i = 0; i < numN; i++) {
				res += Math.abs(wkWk[i] - b);
			}
			System.out.println(res);

		} finally {
			if (scanner != null) {
				scanner.close();
			}
		}
	}

	private void solveD() {
		Scanner scanner = null;
		int numN = 0;
		int numK = 0;
		int numS = 0;

		try {
			scanner = new Scanner(System.in);
			numN = scanner.nextInt();

			System.out.println("");

		} finally {
			if (scanner != null) {
				scanner.close();
			}
		}
	}
}

Measured memory_bytes: 82776
/*   ꧁༒☬महाकाल☬༒꧂ ꧁༒ঔमहाकालঔ༒꧂
                   
                   ঔৣ۝महाकालᴳᵒᵈ۝ঔৣ            
 
 */ 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops"
#include<bits/stdc++.h>
using namespace std;
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//template <typename T, typename cmp=less<T>> using oset =tree<T, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
#define ll long long 
#define mod 1000000007
#define MOD 998244353
#define inf 100000000000000000
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define _it iterator
#define all(_x) _x.begin(),_x.end()
#define f first
#define s second
#define pb push_back
#define ar array
#define ld long double

void mahakal(){
	#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	freopen("error.txt","w",stderr);
	#endif
}
ll dx[4]={1,0,-1,0};
ll dy[4]={0,1,0,-1};
// char c[4]={'D' , 'R' , 'U' , 'L'};
const ll maxN=2e5+5;
ll a, b , c , d;
void solve(){
	cin>>a>>b>>c>>d;
    ll ans = max({max(a,b)*max(c,d) , min(a,b)*max(c,d) , max(a,b)*min(c,d), min(a,b)*min(c,d)   });
    cout<<ans<<endl;
}

int main(){
// 	mahakal();
	fast;
	ll t =1 ;
// 	cin>> t ; 
	while(t--)solve();
// 	cerr << "\ntime taken : " << (float)clock() / CLOCKS_PER_SEC << " secs" << endl; 
	return 0;
}

Measured memory_bytes: 3648
#include <iostream>
#include <cmath>

using namespace std;

int main(){
    double a, b, x, area, ans;
    cin >> a >> b >> x;
    area = x / a;

    if(area >= a * b / 2){
        ans = 90 - atan2(a*a, 2*(a*b - area)) * 180 / M_PI;
    }else{
        ans = atan2(b*b, 2 * area) * 180 / M_PI;
    }
    printf("%.10f\n", ans);
    return 0;
}

Measured memory_bytes: 892
import sys
sys.setrecursionlimit(10**9)
INF = float('inf')

def main():
    n, m, p = map(int,input().split())
    es = []
    for _ in range(m):
        e = list(map(int,input().split()))
        es.append([e[0]-1,e[1]-1,- e[2] + p])

    v_cost = [INF]*n
    v_cost[0] = 0
    for v in range(n*2):
        for e in es:
            frm = e[0]
            to = e[1]
            if v_cost[to] > v_cost[frm]+e[2]:
                v_cost[to] = v_cost[frm]+e[2]
                if v >= n:
                    v_cost[to] = -INF
        if v == n-1:
            prev = v_cost[-1]

    if prev != v_cost[-1]:
        return -1

    return max(0,-v_cost[-1])
   

if __name__ =="__main__":
    print (main())


Measured memory_bytes: 47704
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#include <math.h>
#include <cmath>
#include <ctime>
#include <stdlib.h>

using namespace std;

#define int long long

#define endl "\n"
#define all(v)  v.begin(),v.end()
#define fir first
#define sec second
#define m_p make_pair
#define m_t make_tuple
#define rep(i,n)  for(int i=0; i<(int) (n); i++)
typedef pair<int, int> P;
typedef long double ld;

const double pai = 3.1415926535897;
const int mod = 1000000007;
const int INF = 1000000021;
const int MAX = 510000;
const int MOD = 1000000007;
long long fac[MAX], finv[MAX], inv[MAX];


//x未満の要素数を返す二分探索関数
int b_s(vector<int>& vec, int xx) {
	return lower_bound(all(vec), xx) - vec.begin();
}
template<typename T>void vecout(vector<T>& vec) { for (T t : vec) cout << t << " "; cout << endl; }
template<typename TT>void vecin(vector<TT>& vec) {
	for (int i = 0; i < vec.size(); i++) {
		cin >> vec[i];
	}
}

// テーブルを作る前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

//n個を1個以上のx組のグループに分ける重複組み合わせはcom(n-1,x-1)
long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
long long modpow(int a, int n) {
	int res = 1;
	while (n > 0) {
		if (n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}

bool chmax(int& xx, int yy) {
	if (xx < yy) {
		xx = yy;
		return true;
	}
	return false;
}
bool chmin(int& xx, int yy) {
	if (xx > yy) {
		xx = yy;
		return true;
	}
	return false;
}
double dist(int x, int y) {
	return sqrt(x * x + y * y);
}
double dist(int xx1, int xx2, int yy1, int yy2) {
	return sqrt(abs(xx1 - xx2) * abs(xx1 - xx2) + abs(yy1 - yy2) * abs(yy1 - yy2));
}
int gcd(int xx, int yy) {
	int p = xx;
	int q = yy;
	if (q > p)swap(p, q);
	while (p % q != 0) {
		p %= q;
		swap(p, q);
	}
	return q;
}
int lcm(int xx, int yy) {
	return xx * yy / gcd(xx, yy);
}
bool prime(int xx) {
	if (xx <= 1) {
		return 0;
	}
	for (int i = 2; i * i <= xx; i++) {
		if (xx % i == 0) {
			return 0;
		}
	}
	return 1;
}



signed main() {
	int n;
	cin >> n;
	for (int i = 1; i <= 3500; i++) {
		for (int j = 1; j <= 3500; j++) {
			if ((4 * i * j - j * n - i * n)>=1 &&(i * j * n) % (4 * i * j - j * n - i * n) == 0) {
				cout << i << " " << j << " " << (i * j * n) / (4 * i * j - j * n - i * n) << endl;
				return 0;
			}
		}
	}
}

Measured memory_bytes: 3672
#include<iostream>
#include<iomanip>
#include<math.h>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<complex>
#define REP(i, N) for(ll i = 0; i < N; ++i)
#define FOR(i, a, b) for(ll i = a; i < b; ++i)
#define ALL(a) (a).begin(),(a).end()
#define pb push_back
#define INF (long long)1000000000
#define MOD 1000000007
#define EPS (long double) 1e-8
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> P;
int dh[4] = {1, 0, -1, 0};
int dw[4] = {0, 1, 0, -1};

using namespace std;

int main() {
	ll n, w;
	cin>>n>>w;
	vector<P> itm(n);
	REP(i, n) cin>>itm[i].first>>itm[i].second;
	ll dp[n + 1][100 * n + 1];
	REP(i, 100 * n + 1) dp[0][i] = INF * INF;
	dp[0][0] = 0;
	FOR(i, 1, n + 1) {
		REP(j, 100 * n + 1) {
			if(j >= itm[i - 1].first) dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - itm[i - 1].first] + itm[i - 1].second);
			else dp[i][j] = dp[i - 1][j];
		}
	}
	ll res = 0;
	REP(i, 100 * n + 1) {
		if(dp[n][i] <= w) res = i;
	}
	cout<<res<<endl;
}

Measured memory_bytes: 11024
#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ull unsigned ll
#define pb push_back
#define mp make_pair
 
using namespace std;

int used[1000001];
int used1[1000001];
vector<int>pr;

void fill_prime(){
	for(ll i=2;i<=1000000;i++){
		for(ll j=i*i;j<=1000000;j+=i)used[j]++;
	}
	for(int i=2;i<=1000000;i++)if(used[i]==0)pr.pb(i);
}

int main(){
	int n;cin>>n;
	int a[n+1];
	int k=0;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++){
		used1[a[i]]++;
		k=__gcd(k,a[i]);
	}
	fill_prime();
	bool ind=false;
	
	for(int i=0;i<pr.size();i++){
		int cnt=0;
		for(int j=pr[i];j<=1000000;j+=pr[i])cnt+=used1[j];
		if(cnt>1){
			ind=true;
			break;
		}
	}
	if(ind==false){
		cout<<"pairwise coprime";
		return 0;
	}
	if(k==1){
		cout<<"setwise coprime";
		return 0;
	}
	cout<<"not coprime";
	return 0;
}
	

	



Measured memory_bytes: 15600
a, b, x = map(int,input().split())
import math
if a*a*b/2 >=x:
    degrees = math.degrees(math.atan(a*b*b/(2*x)))
else:
    degrees = math.degrees(math.atan((2*a*a*b-2*x)/(a**3)))
print(degrees)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace __gnu_pbds;
using namespace std;
 
typedef long long int ll;
typedef unsigned long long int sll;
typedef long double ld;
#define A 1000000007
#define D 100000000000000ll
#define B 998244353ll
#define C 1000000000000000000ll
#define M 4000
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define oset tree<pair<ll,ll>, null_type,greater<pair<ll,ll>>, rb_tree_tag,tree_order_statistics_node_update> 
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define mxe(v) *max_element(v.begin(),v.end())
#define mne(v) *min_element(v.begin(),v.end())
#define rev(v) reverse(v.begin(),v.end())
#define sor(v) sort(v.begin(),v.end())
#define bs binary_search
#define lb(v,x) lower_bound(v.begin(),v.end(),x)
#define ub(v,x) upper_bound(v.begin(),v.end(),x)
#define ve vector
#define br break
#define PI acos(-1)
#define subt cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n" 

bool prime[1000005];
ll in[1000005];
void SieveOfEratosthenes() 
{ 
    memset(prime, true, sizeof(prime)); 
    for (int p=2; p*p<=1000000; p++) 
        if (prime[p]) 
            for (int i=p*p; i<=1000000; i += p) 
                prime[i] = false; 
} 

int main() 
{
    FAST;
    SieveOfEratosthenes();
    ve<ll> pri;
    for(int i=2;i<1000001;i++)
        if(prime[i])
        {
            in[i]=(ll)pri.size();
            pri.pb(i);
        }
    ll m=(ll)pri.size();
    ve<bool> ch(m,false); 
    
    ll n;
    cin>>n;
    ve<ll> a(n);
    ve<string> ans(n);
    for(int i=0;i<n;i++)
        cin>>a[i];
    
    ll gc=a[0];
    for(int i=0;i<n;i++)
        gc=__gcd(gc,a[i]);
    ll fi=-1;
    for(int i=n-1;i>=0;i--)
    {
        ll b=0,x=a[i];
        while (x % 2 == 0)  
        {  
            b++;
            x = x/2;  
        }  
        if(b>0)
        {
            if(ch[in[2]])
                fi=1;
            ch[in[2]]=1;
        }
        for (ll j = 3; j*j <= x; j = j + 2)  
        {   
            b=0;
            while (x % j == 0)  
            {  
                b++;
                x = x/j;  
            }  
            if(b>0)
            {
                if(ch[in[j]])
                    fi=1;
                ch[in[j]]=1;
            }
        }  
        if (x > 2)  
        {
            if(ch[in[x]])
                fi=1;
            ch[in[x]]=1;
        }
    }
    
    if(fi==-1)
        cout<<"pairwise coprime";
    if(fi==1 && gc==1)
        cout<<"setwise coprime";
    if(fi==1 && gc!=1)
        cout<<"not coprime";
    subt;
    return 0;
}

Measured memory_bytes: 51784
import java.io.*;

public class Main {
  
  public static void main(String[] args) throws Exception {
    
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    String[] in = br.readLine().split(" ");

    br.close();
    
    PrintWriter out = new PrintWriter(System.out);
    out.println(in[0].equals("ABC") ? "ARC" : "ABC");
    out.flush();

  }
}

Measured memory_bytes: 32520
#include<bits/stdc++.h>
#define rep(i,n)for(int i=0;i<n;i++)
#define l long long
using namespace std;l q,x,y,f[99]={0,1},m=1e9+7;main(){cin>>q;rep(i,97)f[i+2]=f[i]+f[i+1];rep(i,q){cin>>x>>y;if(x>y)swap(x,y);if(y<=2){cout<<1<<" "<<(y==1?1:x==1?2:4)<<" ";continue;}rep(j,99){if(x<f[j]||y<f[j+1]){l a=x==1?2:1;rep(k,j-2){l n=f[j-1]+f[j-3-k]*f[k+2],m=f[j]+f[j-2-k]*f[k+2];if(n<=x&&m<=y)a+=(y-m)/n+1;}if(f[j]<=x){a++;rep(k,j-2)a+=(x-f[j])/(f[j-2-k]*f[k+2]);}cout<<j-2<<" "<<a%m<<" ";j=99;}}}}

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

int ask(vector<int> a){
	cout << '?';
	for(int x : a){
		cout << ' ' << x + 1;
	}
	cout << '\n';
	cout << flush;
	string s;
	cin >> s;
	if(s == "-1") exit(0);
	if(s == "Red") return 0;
	if(s == "Blue") return 1;
	assert(false);
}

void answer(vector<int> a){
	cout << "! ";
	for(int x : a){
		if(x == 0){
			cout << "R";
		} else{
			cout << "B";
		}
	}
	cout << '\n';
	cout << flush;
}


int main(){
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	mt19937 mt(48);
	int n;
	cin >> n;
	vector<int> q;
	for(int i = 0; i < 2*n; i++) q.push_back(i);
	shuffle(q.begin(), q.end(), mt);

	auto ask_interval = [&](int i) -> int {
		vector<int> balls(n);
		for(int j = 0; j < n; j++) balls[j] = q[i + j];
		int v = ask(balls);
		return v;
	};
	
	int s = 0;
	int e = n;
	int vs = ask_interval(0);
	int ve = ask_interval(n);
	while(s + 1 < e){
		int m = (s + e) / 2;
		int vm = ask_interval(m);
		if(vm == vs){
			s = m;
		} else {
			e = m;
		}
	}
	vector<int> half1, half2;
	for(int j = e; j < e+n-1; j++){
		half1.push_back(q[j]);
		half2.push_back(q[(j+n) % (2*n)]);
	}
	vector<int> color(2*n);
	color[q[s]] = vs;
	color[q[s+n]] = ve;
	for(int x : half1){
		vector<int> c = half2;
		c.push_back(x);
		color[x] = ask(c);
	}
	for(int x : half2){
		vector<int> c = half1;
		c.push_back(x);
		color[x] = ask(c);
	}
	answer(color);
}

Measured memory_bytes: 724
#include <bits/stdc++.h>
using namespace std;
/*{{{*/  //template
#define rep(i,n) for(int i=0;i<n;i++)
constexpr int INF = numeric_limits<int>::max()/2;
constexpr long long LINF = numeric_limits<long long>::max()/3;
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define sz(x) (int)(x).size()
#define debug(x) cerr<<#x<<":"<<x<<endl
#define debug2(x,y) cerr<<#x<<","<<#y":"<<x<<","<<y<<endl
//struct fin{ fin(){ cin.tie(0); ios::sync_with_stdio(false); } } fin_;
struct Double{ double d; explicit Double(double x) : d(x){} };
ostream& operator<<(ostream& os,const Double x){ os << fixed << setprecision(20) << x.d; return os; }
template<typename T> ostream& operator<<(ostream& os,const vector<T>& vec){ os << "["; for(const auto& v : vec){ os << v << ","; } os << "]"; return os; }
template<typename T,typename U> ostream& operator<<(ostream& os,const pair<T,U>& p){ os << "(" << p.first << ","<< p.second <<")"; return os; }
template<typename T> ostream& operator<<(ostream& os,const set<T>& st){ os<<"{"; for(T v:st) os<<v<<","; os <<"}"; return os; }
template<typename T,typename U> inline void chmax(T &x,U y){ if(y>x) x = y; }
template<typename T,typename U> inline void chmin(T &x,U y){ if(y<x) x = y; }
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
ll gcd(ll a,ll b){ if(b==0) return a; else return gcd(b,a%b); }
//constexpr double eps = 1e-14; 
constexpr double eps = 1e-10; 
constexpr ll mod = 1e9+7;
const int dx[]={1,0,-1,0} ,dy[] = {0,1,0,-1};
/*}}}*/

string s;

int main(){
    cin >> s;

    int n = s.size();
    rep(i,n)rep(j,n) if(i!=j){
        if(s[i]==s[j]){
            cout << "no"<< endl;
            return 0;
        }
    }
    cout << "yes" << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A,s1,s2,s3;

  cin >> A;
  s1=A/100;
  s3=A%10;
  s2=(A-s1*100-s3)/10;
 cout <<s1+s2+s3 <<endl;
}


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

int main(){
  ll n,m;cin>>n>>m;
  ll a[m+10],b[n+10]={1,1},mod=7+1e9,sum=1;
  for(ll i=0;i<m;i++){
    cin>>a[i];
    if(i==0)continue;
    if(a[i]-a[i-1]==1){cout<<0;return 0;}
  }
  rep(i,n-1)b[i+2]=b[i]%mod+b[i+1]%mod;
  //cout<<b[10000]<<endl;
  for(ll i=0;i<m;i++){
    if(i==0)sum*=b[a[i]-1]%mod;
    else{
      sum*=b[a[i]-a[i-1]-2];
      sum%=mod;
      }
  }

  if(m==0)cout<<b[n]%mod<<endl;
  else{
    sum*=b[n-a[m-1]-1]%mod;
    cout<<sum%mod<<endl;
  }
}

Measured memory_bytes: 1408
#!/usr/bin/env python3
#ABC132 B
import sys
sys.setrecursionlimit(1000000)
from collections import deque

N = int(input())
P = list(map(int,input().split()))
ans = 0
for i in range(1,N-1):
    if max(P[i-1],P[i],P[i+1]) == P[i]:
        continue
    elif min(P[i-1],P[i],P[i+1]) == P[i]:
        continue
    else:
        ans += 1
print(ans)


Measured memory_bytes: 3444
K, A, B = map(int, input().split())
# 1円に交換するためにはA枚のビスケットがいる　操作１
# B枚のビスケットにするためには1円がいる　操作２
# 持っているビスケット(０個でもいい)を叩けば一個ビスケットが得られる　操作３

# A > B
# A == B
# A < B

if (K == 1):
    print(K + 1)
    exit()

if (A >= B):
    print(K + 1)
    exit()

elif (A < B):
    # 1円を作るたびに操作３を実行
    nokori = K - (A - 1)
    bis = A
    for _ in range(A):
        if (nokori % 2 != 0):
            nokori -= 1
            bis += 1
        else:
            break

    if (bis + ((B - A) * (nokori // 2)) >= 1 + K):
        print(bis + ((B - A) * (nokori // 2)))
    else:
        print(1 + K)


Measured memory_bytes: 61876
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define vmin(vec) *min_element(vec.begin(), vec.end())
#define vmax(vec) *max_element(vec.begin(), vec.end())
#define len(array) (sizeof(array) / sizeof(array[0]))

int main() {
  long n;cin>>n;
  auto m=n;
  int fx=0;
  while (m>0) {
    fx += m%10;
    m /= 10;
  }
  if (n % fx == 0) cout << "Yes";
  else cout << "No";
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;

template<typename T>
struct Matrix 
{
    vector<vector<T> > mat;
    int n;
    Matrix(T n)
    {   this->n = n;
        mat.resize(n,vector<T> (n));
    }
    Matrix operator*(const Matrix &b)
    {
        Matrix<T> c(n); 
        for(int i = 0; i< n;i++){
            for(int j = 0; j<n; j++){
                for(int k = 0; k<n; k++)
                    c.mat[i][j] = (c.mat[i][j]  + (mat[i][k]*b.mat[k][j])%MOD)%MOD;
            }                
        }
        return c;
    }
    Matrix binpow (ll k)
    {
        Matrix<T> ans(n);
        for(int i =0; i<n; i++) ans.mat[i][i] = 1LL;

        while(k>=1)
        {
            if(k&1)
                ans = (ans*(*this));
            *(this) = (*this) * (*this);
            k>>=1;
        }
        return ans;
    }
};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n,  k;
    cin>>n>>k;
    Matrix<ll> m(n);
    for(int i =0; i<n; i++)
        for(int j = 0; j< n; j++)
            cin>>m.mat[i][j];

    Matrix<ll> res(n);
    res = m.binpow(k);

    ll ans = 0;
    for(int i =0; i<n; i++){
        for(int j = 0; j<n; j++){
            ans = (ans + res.mat[i][j])%MOD;
        }
    }
    cout<<ans<<"\n";
    
}

Measured memory_bytes: 384
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))
s = input()
t = input()

ans = 0
for i in range(3):
    if s[i] == t[i]: ans += 1
print(ans)

Measured memory_bytes: 5048
import java.util.*;
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String a = sc.next();
    String b = sc.next();

    String str = a + b;
    int c = Integer.parseInt(str);

    for (int i = 1; i <= 1000 ; i++ ) {
      if ((i * i) == c) {
        System.out.println("Yes");
        return;
      }
    }
    System.out.println("No");
  }
}


Measured memory_bytes: 21716
n = int(input())
w = [input() for i in range(n)]

s = set([])
s.add(w[0])
word = w[0][-1]

for i in range(1, n):
    if w[i] in s:
        print("No")
        exit()
    if w[i][0] != word:
        print("No")
        exit()
    s.add(w[i])
    word = w[i][-1]

print("Yes")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
const int mod=1e9+7;
map<ll,ll> mp,flag;
ll a[N],cnt[N],b[N];
int k;
string s;
int main() {;
//   freopen("../in.in", "r", stdin);
//    freopen("../out.out","w",stdout);
    ios::sync_with_stdio(false);
    int t,i,j=0;
    int m,x,n,y;
    cin>>n;
    ll ans=0;
    for(i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]<a[i-1]){
            ans+=a[i-1]-a[i];
            a[i]=a[i-1];
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 5216
#include<bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define int long long
#define vec(a,n) vector<int> (a)((n));
#define Vec(a,n) vector<string> (a)((n));
#define twovec(a,n,m) vector<vector<int>> a(n,vector<int>(m,0));
#define Twovec(a,n,m) vector<vector<double>> a(n,vector<double>(m,0));
#define P pair<int,int>
#define All(a) (a).begin(),(a).end()
#define Sort(a) sort(All(a));
#define Reverse(a) reverse(All(a));
#define PQ(n) priority_queue<P,vector<P>,greater<P>> (n)
#define pq(n) priority_queue<int> (n)
#define print(a) cout << (a) << endl;
#define printD(a) cout << setprecision(6) << (a) << endl;
using namespace std;
int max_int = 1000000007;
void Debug(auto a);
int nibul(auto a,auto b);
int nibuu(auto a,auto b);
void input(vector<int>& a,int n);

int n;

signed main(){

    while(1){
        int h,w;
        cin >> h >> w;
        if(h==0 && w==0){
            break;
        }
        REP(i,h){
            REP(j,w){
                if(i == 0 || i == h-1){
                    cout << "#";
                }
                else{
                    if(j == 0 || j == w-1){
                        cout << "#";
                    }
                    else{
                        cout << ".";
                    }
                }
            }
            cout << endl;
        }
        cout << endl;
    }

    return 0;
}

void Debug(auto a){
    cout << "{ ";
    for(auto b: a){
        cout << b << " ";
    }
    cout << "}" << endl;
}
int nibul(auto a,auto b){
    int x = lower_bound(All(a),b) - a.begin();
    //key以上の初めてのitr
    return x;
}
int nibuu(auto a,auto b){
    int x = upper_bound(All(a),b) - a.begin();
    //key以下の最後のitr
    return x-1;
}

void input(vector<int>& a,int n){
    REP(i,n){
        cin >> a[i];
    }
}



Measured memory_bytes: 3096
//minamoto
#include<bits/stdc++.h>
#define R register
#define res register int
#define se second
#define fi first
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
const int N=1e5+10;
namespace MAIN{
	typedef pair<int,int> Pair;
    int n,k;
    char str[N];
    int ans;
    Pair a[2][N];
    int b[2];
    int st,ed;
    inline void MAIN(){
        scanf("%d%d%s",&n,&k,str+1);
        for(res i=1;i<=n;){
            res j=i;
            while(str[j]==str[i]&&j<=n)j++;
            j--;
            if(str[i]=='L')a[0][++b[0]]=make_pair(i,j);
            else a[1][++b[1]]=make_pair(i,j);
            i=j+1;
        }
        st=str[1]=='R';
        ed=str[n]=='R';
        for(res i=1;i<=b[0];i++)ans+=a[0][i].se-a[0][i].fi;
        for(res i=1;i<=b[1];i++)ans+=a[1][i].se-a[1][i].fi;
        if(b[0]<=k){printf("%d\n",n-1);return;}
        if(b[1]<=k){printf("%d\n",n-1);return;}
        if(st==ed){
            printf("%d\n",ans+2*k);
            return;
        }
        printf("%d\n",ans+2*k);
    }
}
int main(){
    MAIN::MAIN();
    return 0;
}

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

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

//container util
#define all(x) (x).begin(),(x).end()

//typedef
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VLL;
typedef vector<VLL> VVLL;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;


//conversion
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

const int num[] = {-1,2,5,5,4,5,6,3,7,6};
int main(){
  ll N,M;
  cin >> N >> M;
  VLL a(M);
  VLL A(M);

  vector<PII> Ap;
  rep(i,M){
     cin >> a[i];
     Ap.push_back( make_pair(num[a[i]],i) );
  }
  sort(all(Ap));
  rep(i,M) A[i] = a[Ap[i].second];

  vector<char> numChar;
  rep(i,M){
    string s = toString(A[i]);
    numChar.push_back(s[0]);
  }
  
  vector<string> dp(10101,"x");

  //達成できる最大桁数を計算する。

  dp[0] = "";

  rep(i,M){
    rep(j,N-num[ A[i] ]+1)
      if(dp[j] != "x"){
        if(dp[ j + num[ A[i] ] ] != "x"){
          //長さ比較
          if(dp[ j + num[ A[i] ] ].size() <  dp[j].size() + 1) dp[ j + num[ A[i] ] ] = dp[j] + numChar[i];
          else if(dp[ j + num[ A[i] ] ].size() >  dp[j].size() + 1) continue;
          else if(dp[ j + num[ A[i] ] ].size() == dp[j].size() + 1){
            //文字列辞書式順比較
            string headS = dp[j] + numChar[i];
            string tailS = numChar[i] + dp[j];
            dp[ j + num[ A[i] ] ] = max(tailS,max(headS,dp[ j + num[ A[i] ] ]));
          }
        }
        else{
          //文字列辞書式順比較
          string headS = dp[j] + numChar[i];
          string tailS = numChar[i] + dp[j];
          dp[ j + num[ A[i] ] ] = max(tailS,headS);
        }
      }
  }

  cout << dp[N] << endl;

  return 0;
}


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

int main(){
    queue<string> names;
	queue<int> times;
    int n, q, time;
	string name;
	cin >> n >> q;
    for (int i = 0; i < n; i++){
		cin >> name;
		cin >> time;
		names.push(name);
		times.push(time);
	}
    int t = 0;
    while (!names.empty() && !times.empty()){
        if (times.front() > q){
            t += q;
            times.push(times.front() - q);
            names.push(names.front());
            times.pop();
            names.pop();
        }else{
            t += times.front();
            cout << names.front() << ' ' << t << endl;
            times.pop();
            names.pop();
        }
    }
}

Measured memory_bytes: 5692
#include <bits/stdc++.h>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#define nl "\n"
#define for(variable,initial,final) for(variable=initial;variable<final;++variable)
using namespace std;
int main()
{
     int a;
     cin>>a;
    cout<<(a+pow(a,2)+pow(a,3))<<nl;
        

 return 0;
}


Measured memory_bytes: 4132
#AGC018-A
if True:
    import fractions

    N,K=map(int,input().split())
    A=[int(i) for i in input().split()]
    MAX=max(A)
    GCD=A[0]
    for a in A:
        GCD=fractions.gcd(a,GCD)
    if K%GCD==0 and K<=MAX:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')
    

Measured memory_bytes: 16028
def up_to_you(formula):
    l_p = None
    r_p = None
    for i, c in enumerate(formula):
        if c == '(':
            l_p = i
        elif c == ')':
            r_p = i
            break
    else:
        print fx(formula)
        return
    
    r = fx(formula[l_p+1:r_p])
    n_formula = formula[:l_p]+r+formula[r_p+1:]
    return up_to_you(n_formula)
            
def fx(gemstone):
    n = ''
    lis = []
    add = ''
    if gemstone[0] == '-':
        gemstone = gemstone[1:]
        add = '-'
    for c in gemstone:
        if c.isdigit():
            n += c
        else:
            if n == '':
                add = '-'
            else:
                lis.append(add+n)
                lis.append(c)
                n = ''
                add = ''
    else:
        lis.append(add+n)
    return isolation(lis)
    
def isolation(lis):
    if len(lis) == 1:
        return str(lis[0])
    o1 = None
    o = None
    o2 = None
    o_i = None
    n_lis = None
    if '*' in lis or '/' in lis:
        for i, v in enumerate(lis):
            if o1 == None:
                o1 = v
            elif v == '*' or v == '/':
                o = v
                o_i = i
            elif v == '+' or v == '-':
                o1 = None
            else:
                o2 = v
                r = discomfort(int(o1), o, int(o2))
                n_lis = lis[:(o_i-1)]+[r]+lis[(o_i+2):]
                return isolation(n_lis)
    else:
        o1 = lis[0]
        o = lis[1]
        o2 = lis[2]
        o_i = 1
        r = discomfort(int(o1), o, int(o2))
        n_lis = lis[:(o_i-1)]+[r]+lis[(o_i+2):]
        return isolation(n_lis)
                
def discomfort(o1, o, o2):
    r = None
    if o == '*':
        r = o1 * o2
    elif o == '/':
        r = o1 / o2
        if o1 < 0 and o1 % o2 != 0: r += 1
    elif o == '+':
        r = o1 + o2
    elif o == '-':
        r = o1 - o2
    return str(r)
    
if __name__ == '__main__':
    N = int(raw_input())
    for i in range(N):
        formula = raw_input().rstrip('=')
        up_to_you(formula)

Measured memory_bytes: 4384
def hersCode(l, r):
  ok = r
  ng = l - 1
  while ok - ng > 1:
    mid = (ok + ng) // 2
    if nasu(a[mid]):
      ok = mid
    else:
      ng = mid
  return ok

def nasu(x):
  if x >= K:
    return True
  D = [0] * K
  L = [0]
  f = 0
  for i in a:
    if i == x and f == 0:
      f = 1
      continue
    for jj in range(len(L) - 1, -1, -1):
      j = L[jj]
      if i + j < K:
        if i + j + x >= K:
          return True
        if D[i + j] == 0:
          D[i + j] = 1
          L.append(i + j)
  return False


N, K = list(map(int, input().split()))
a = list(map(int, input().split()))

a.sort()
a.append(10 ** 9 + 1)
ans = hersCode(0, N)
print(ans)

Measured memory_bytes: 40812
/*
 * Author:  heyuhhh
 * Created Time:  2020/5/16 11:11:17
 */
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <assert.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
  #define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
  void err() { std::cout << std::endl; }
  template<typename T, typename...Args>
  void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
  template <template<typename...> class T, typename t, typename... A> 
  void err(const T <t> &arg, const A&... args) {
  for (auto &v : arg) std::cout << v << ' '; err(args...); }
#else
  #define dbg(...)
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 2e5 + 5;

int n;
int a[N];
ll dp[N], pre[N];

void run() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    reverse(a + 1, a + n + 1);
    pre[1] = a[1];
    for (int i = 3; i <= n; i++) {
        pre[i] = pre[i - 2] + a[i];
    }
    for (int i = 2; i <= n; i += 2) {
        dp[i] = dp[i - 2] + a[i];
        if (i >= 3) dp[i] = max(dp[i], pre[i - 3] + a[i]);
    }
    reverse(a + 1, a + n + 1);
    ll ans = -1e18;
    if (n % 2 == 0) {
        ans = max(pre[n - 1], dp[n]);
    } else {
        ll now = 0;
        int cnt = 0;
        for (int i = 1; i <= n && cnt < n / 2; i += 2, ++cnt) {
            ans = max(ans, now + dp[n - i]);
            ans = max(ans, now + pre[n - i - 1]);
            now += a[i];
        }
        ans = max(ans, now);
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20);
    run();
    return 0;
}

Measured memory_bytes: 7516
#include<bits/stdc++.h>
using namespace std;
#define con continue
#define bk break
#define LL long long
#define db double
#define pt cout<<'\n'
#define ms(a, b) memset((a), (b), sizeof(a))
#define mp make_pair
#define endl '\n'
int inf=2147483647;const long long ll =9223372036854775807,ninf=1000000000;const double eps = 1e-6; const long long nll =223372036854775807;
#define sz size()
#define len(X) strlen(X)
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ULL unsigned long long
#define de cout<<"test"<<endl;
#define st system("pause");
#define M_PI 3.1415926
int main()
{
   int a;
   while(cin>>a){
    int cnt[26]={};
    for(int i=0;i<26;i++)
        cnt[i]=inf;
    for(int i=0;i<a;i++){
        string x;
        cin>>x;
        int tmp[26]={};
        for(int j=0;j<x.sz;j++){
            tmp[x[j]-'a']++;
        }
        for(int j=0;j<26;j++){
            cnt[j]=min(cnt[j],tmp[j]);
        }
    }
    for(int i=0;i<26;i++){
        for(int j=0;j<cnt[i];j++){
            cout<<char(i+'a');
        }
            }
    pt;




   }
    return 0;
}


Measured memory_bytes: 256
a,b,c = map(int, input().split())
k = int(input())

for ai in range(k+1):
    for bi in range(k+1):
        for ci in range(k+1):
            if not (ai + bi + ci == k):
                continue
            newA = a * (2 ** ai)
            newB = b * (2 ** bi)
            newC = c * (2 ** ci)

            if newB > newA and newC > newB:
                print('Yes')
                exit()

print('No')

Measured memory_bytes: 9192
s=gets.to_i
for i in 1..s
    gets
    num=[]
    8.times do
        num<<gets.chomp.split(//).map(&:to_i)
    end
    x=gets.to_i-1
    y=gets.to_i-1
    
    check=[x,y]
    until check.empty?
        x=check.shift
        y=check.shift
        
        (-3).upto(3) do |t|
            if (x+t)<8 && 0<=(x+t) && num[y][x+t]==1
                check<<(x+t).to_i
                check<<y.to_i
                num[y][x+t]=0
            end
            if (y+t)<8 && 0<=(y+t) && num[y+t][x]==1
                check<<x.to_i
                check<<(y+t).to_i
                num[y+t][x]=0
            end
        end
    end
    puts "Data #{i}:"
    8.times{ |t| puts num[t].join}
end

Measured memory_bytes: 6120
n = int(input())
card = []
for suit in range(4):
    st = []
    for rank in range(14):
        st.append(False)
    card.append(st)
    
for i in range(n):
    suit, rank = input().split()
    suit = 'SHCD'.index(suit)
    rank = int(rank)
    card[suit][rank] = True

for suit in range(4):
    for rank in range(1, 14):
        if card[suit][rank] == False:
            print('SHCD'[suit], rank)
    


Measured memory_bytes: 5596
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1000000000;
const int MOD = (int)1e9 + 7;

signed main()
{
    int n, m;
    cin >> n >> m;
    map<int, int> a;
    for (int i = 0; i < m; i++)
    {
        int x;
        cin >> x;
        a[x]++;
    }
    vector<int> v;
    v.push_back(1);
    v.push_back(1);
    for (int i = 2; i < n + 1; i++)
    {
        int r;
        if (a[i - 1] && a[i - 2])
        {
            cout << 0 << "\n";
            return 0;
        }
        else if (a[i - 1])
            r = v[i - 2];
        else if (a[i - 2])
            r = v[i - 1];
        else
            r = v[i - 1] + v[i - 2];
        v.push_back(r % MOD);
    }
    cout << v[n]<< "\n";
}

Measured memory_bytes: 7284
#include<iostream>
#include<vector>
#include<iomanip>
using namespace std;
const int N=3000;
double dp[N][N],sum=0;
double p[N];
int main(){
	int n,i,j;
	cin>>n;
	for(i=1;i<=n;i++){
		cin>>p[i];
	}
	dp[0][0]=1.0;
	for(i=1;i<=n;i++){
		for(j=0;j<=i;j++){
			if(j>0){
				dp[j][i-j]=p[i]*dp[j-1][i-j];
			}
			if(j<i){
				dp[j][i-j]+=(1-p[i])*dp[j][i-j-1];
			}
			if(i==n&&2*j>=i){
				sum+=dp[j][i-j];
			}
		}
	}
	cout<<fixed<<setprecision(9)<<sum;
}


Measured memory_bytes: 70016
/*
Author: Racer5x
 ***************************************   UNAUTHORISED COPYING OF CODE PROHIBITED   **********************************
*/
 
// #pragma GCC optimize("O3")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
#include<bits/stdc++.h>
#define int         long long
#define double      long double
#define pb          emplace_back
#define pf          emplace_front
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define rall(a)     (a).rbegin(),(a).rend()
#define x           first
#define y           second
#define endl        '\n'
#define hell        998244353 
#define PI          3.141592653589
#define tezz        ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define MAX         2000000000000000000
#define M           1000000007
 
using namespace std;
 
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
int power(int x,int n){
    int result=1;
    while(n>0)
    {
        if(n % 2 ==1)
            result=(result * x) % hell;
        x=(x*x) % hell;
        n=n/2;
    }
    return result % hell;
}
 
class dsu{
    vi p,rank;
    vi set_count;
  
  public:
    dsu(int n){
        p.assign(n,0); 
        rank.assign(n,0);
        set_count.assign(n,1);
        for(int i=0;i<n;i++) p[i] = i;
    }
    int findSet(int x){
        return (p[x] == x) ? x:(p[x] = findSet(p[x]));
    }
    bool isSame(int i, int j){
        return (findSet(i) == findSet(j));
    }
    void unionSet(int i, int j){
        if(!isSame(i,j)){
            int x = findSet(i), y = findSet(j);
            if(rank[x] > rank[y]) {p[y] = x; set_count[x]+=set_count[y];}
            else{
                p[x] = y;
                set_count[y]+=set_count[x];
                if(rank[x] == rank[y]) rank[y]++;
            }
        }
    }
    int count(int x){
        return set_count[findSet(x)];
    }
};

int S[105][105];
int T[105][105];

// code copied from god_arham
int mod_inv(int a,int m){
    a=a%m;
    return power(a,m-2)%hell;
}
int fact[200005];
void count_fact(){
    int i,x=1;
    fact[0]=1;
    for(int i=1;i<200002;i++){
        
        x=(x*i)%hell;
      //  cout<<x<<" ";
        fact[i]=x;
        
    }
}
 
int ncr(int n,int r){
    int a=fact[n],b=fact[r],c=fact[n-r];
    
    return (a*mod_inv(b*c,hell))%hell;
} 
//copied code ends here
 
signed main()
{
    tezz
 
    int n;
    cin>>n;

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

    for(int i=0;i<n;i++) cout<<s[i]<<t[i];
}

Measured memory_bytes: 256
n = gets.to_i

a = []
[6,9].each{|t|
  w = t
  while w <= 100000
    a << w
    w *= t
  end
}
a.sort!

dp = [*0..100000]
a.each{|t|
  100001.times{|i|
    if 0<=i-t && dp[i-t]+1 < dp[i]
      dp[i] = dp[i-t]+1
    end
  }
}

p dp[n]

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

#define endl "\n"
#define all(V) V.begin(),V.end()
#define see(x) cerr << #x << " = " << x << "\n";
#define Unique(V) sort(all(V)),V.erase(unique(all(V)),V.end())
#define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long int LL;
typedef pair <int,int> pii;
const int MOD = 1e9 + 7;
const int inf = 1e9;
const double PI = acos(-1.0);
const long long INF = 1e18;
const int N = 100 + 5;

int n, cap;
LL w[ 105 ] , v[ 105 ];
LL dp[ 105 ][ 100005 ];

int main( ) {
        IO;
        cin >> n >> cap;
        for( int i = 1; i <= n; i++ ) cin >> w[i] >> v[i];
        for( int i = n; i >= 1; i-- ) {
                for( int c = 1; c <= cap; c++ ) {
                        if( w[i] <= c ) {
                                dp[i][c] = max( dp[i+1][c] , dp[i+1][c-w[i]] + v[i] );
                        }
                        if( i != n ) dp[i][c] = max( dp[i][c] , dp[i+1][c] );
                }
        }
        cout << dp[1][cap] << endl;
        return 0;
}









Measured memory_bytes: 79360
#include <iostream>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <map>
#include <queue>
#include <string>
#include <vector>
#include <ostream>
#include <cstring>
#include <cmath>

using std::cin;
using std::cout;
using std::cerr;
using std::endl;

template<typename T, typename U>
std::ostream& operator << (std::ostream& os, std::pair<T, U> p) {
  os << "(" << p.first << ", " << p.second << ")";

  return os;
}

template<typename T>
std::ostream& operator << (std::ostream& os, std::vector<T> v) {
  os << "[";
  for (int i = 0; i < int(v.size()); ++i) {
    os << v[i] << (i + 1 == int(v.size()) ? "" : " ");
  }
  os << "]";

  return os;
}

inline void init() {
  cin.tie(0);
  std::ios::sync_with_stdio(false);
}

int main() {
  init();

  int n;

  cin >> n;

  int ans = 0, dp[100001];

  std::vector<int> v(1, 1);

  for (int i = 1; i < 8; ++i) {
    if (pow(6, i) <= n) v.push_back(pow(6, i));
    if (pow(9, i) <= n) v.push_back(pow(9, i));
  }

  std::memset(dp, 0x7f, sizeof dp);
  dp[0] = 0;

  for (int i = 0; i <= n; ++i) {
    for (int j = 0; j < v.size(); ++j) {
      if (i + v[j] <= n) {
        dp[i + v[j]] = std::min(dp[i] + 1, dp[i + v[j]]);
      }
    }
  }

  cout << dp[n] << endl;

  system("pause");
  return 0;
}


Measured memory_bytes: 1024
N = int(input())
A = list(map(int,input().split()))
A.append(0)
A.insert(0,0)
S = 0

for i in range(len(A)-1):
    S+=abs(A[i+1]-A[i])#総コスト
    
for i in range(1,N+1):
    print(S-abs(A[i]-A[i-1])-abs(A[i+1]-A[i])+abs(A[i+1]-A[i-1]))





Measured memory_bytes: 20544
#include <bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<n;i++)
#define all(a) a.begin(),a.end()
#define o(a) cout<<a<<endl
#define int long long
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

signed main(){
	int n;
	while(cin>>n && n>0){
		vector<pii> d(n);
		rep(i,0,n) cin>>d[i].second>>d[i].first;
		sort(all(d));

		int now=0;
		bool f=true;
		rep(i,0,n){
			now+=d[i].second;
			if(now>d[i].first) f=false;
		}
		o((f?"Yes":"No"));
	}
}

Measured memory_bytes: 1192
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
using namespace std;
using Graph = vector<vector<int>>;
typedef pair<int,int> P;
typedef long long ll;

int main(){
	int n; cin >> n;
    set<string> st;
    rep(i,n){
        string s; cin >> s;
        st.insert(s);
    }

    int m; cin >> m;

    bool jud = true;
    rep(i,m){
        string t; cin >> t;
        if(st.count(t)){
            if(jud){
                cout << "Opened by " << t << endl;
                jud = false;
            }
            else{
                cout << "Closed by " << t << endl;
                jud = true;
            }
        }

        else{
            cout << "Unknown " << t << endl;
        }
    }
}


Measured memory_bytes: 3224
import java.util.*;
import java.io.*;
public class Main
{
    static BufferedWriter bw;
    static BufferedReader br;
    static void solve()throws Exception
    {
        int nm[] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int A[] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        long sum = 0;;
        for(int temp:A)
        {
            sum+=temp;
        }
        if(sum>nm[0])
        bw.write("-1");
        else
        bw.write(Long.toString(nm[0]-sum));
    }
    public static void main(String []args)throws Exception
    {
        br=new BufferedReader(new InputStreamReader(System.in));
        bw=new BufferedWriter(new OutputStreamWriter(System.out));
        // int t = Integer.parseInt(br.readLine());
        // for(int i=0;i<t;i++)
        // {
        //     bw.write("Case #"+(i+1)+": ");
            solve();
        // }
        br.close();
        bw.close();
    }
}


Measured memory_bytes: 32536
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main(){
  int i,j,n,p[200000],count=0,ans=0;
  scanf("%d",&n);
  
  for(i=0;i<n;i++){
    scanf("%d",&p[i]);
  }
  int min=p[0];
  //int total=p[0];
  for(i=1;i<n;i++){
    if(min>p[i]){
      min=p[i];
      ans++;
    }
  }
  printf("%d\n",ans+1);
  return 0;
}

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


// UnionFind
struct UnionFind {
    vector<int> d;
    UnionFind(int n=0) : d(n, -1) {} // 各ルートノードはサイズのマイナスを値にもつ
    int find(int x) {
        if (d[x] < 0) return x;
        return d[x] = find(d[x]);
    }
    bool unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return false;
        if (-d[x] < -d[y]) swap(x,y); // Xの方がサイズが大きくなるように
        d[x] += d[y];                   // サイズを更新
        d[y] = x;                       // 大きいツリーに小さいツリーを足す
        return true;
    }
    bool same(int x, int y) {return find(x) == find(y);}
    int size(int x) {return -d[find(x)];}
};


int friends[100005];
vector<int> bl[100005];

int main(){
    int n, m, k;
    cin >> n >> m >> k;
    
    UnionFind un(n);

    // 友達関係
    rep(i, m) {
        int a, b;
        cin >> a >> b;
        a--;b--;
        friends[a]++;
        friends[b]++;
        un.unite(a, b);
    }

    // ブロック
    rep(i,k) {
        int c, d;
        cin >> c >> d;
        c--;d--;
        bl[c].push_back(d);
        bl[d].push_back(c);        
    }

    // 友達候補のカウント
    rep(i,n) {
        int ans = 0;
        ans = un.size(i) - friends[i] -1; // 友達連結成分内のノード数から、自身の友達数と自分自身を引く
        for (auto x : bl[i]) {
            if (un.same(i, x)) ans--;  // 同じ連結成分内のブロック者は、候補から引く
        }
        printf("%d%c", ans, i==n-1?'\n':' ');
    }   

    return 0;
}


Measured memory_bytes: 6784