akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>
#include<iomanip>
#include<queue>
#include<stack>
#include<time.h>
#define rep(i,n)for(int i=0;i<n;i++)
#define int long long
#define ggr getchar();getchar();return 0;
#define prique priority_queue
#define mod 1000000007
#define inf 1e15
#define key 1e9
using namespace std;
typedef pair<int, int>P;
void yes() { cout << "Yay!" << endl; }
void no() { cout << ":(" << endl; }
template<class T> inline void chmax(T& a, T b) {
	a = std::max(a, b);
}
template<class T> inline void chmin(T& a, T b) {
	a = std::min(a, b);
}
const int MAX = 330000;
int fac[MAX], finv[MAX], inv[MAX];
// テーブルを作る前処理
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;
	}
}

// 二項係数計算
long long COMB(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;
}
bool prime(int n) {
	int cnt = 0;
	for (int i = 1; i <= sqrt(n); i++) {
		if (n % i == 0)cnt++;
	}
	if (cnt != 1)return false;
	else return n != 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x / gcd(x, y) * y;
}
int kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= i; res %= mod;
	}
	return res;
}
int mod_pow(int x, int y, int m) {
	int res = 1;
	while (y) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}
int comb(int x, int y) {
	if (y > x)return 0;
	return kai(x, y)* mod_pow(kai(y, y), mod - 2, mod) % mod;
}
void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
	cerr << " " << to_string(H);
	debug_out(T...);
}

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
struct edge { int to, cost; };
int par[114514], rrank[114514];//親、木の深さ
void init(int n) {
	rep(i, n) {
		par[i] = i;
		rrank[i] = 0;
	}
}
int find(int x) {
	if (par[x] == x) {
		return x;
	}
	else return par[x] = find(par[x]);
}
void unite(int x, int y) {
	x = find(x);
	y = find(y);
	if (x == y)return;
	if (rrank[x] < rrank[y]) {
		par[x] = y;
	}
	else {
		par[y] = x;
		if (rrank[x] == rrank[y])rrank[x]++;
	}
}
bool same(int x, int y) {
	return find(x) == find(y);
}
int n;
int x[114514], l[114514];
P a[114514];
signed main() {
	cin >> n;
	rep(i, n)cin >> x[i] >> l[i];
	rep(i, n) {
		a[i].first = x[i] - l[i];
		a[i].second = x[i] + l[i];
	}
	sort(a, a + n);
	int memo = a[0].second;
	int ans = 0;
	for (int i = 1; i < n; i++) {
		if (memo > a[i].first) {
			ans++;
			memo = min(memo, a[i].second);
		}
		else memo = a[i].second;
	}
	cout << n - ans << endl;
	ggr
}


Measured memory_bytes: 4096
#include<stdio.h>
unsigned int N,i,A[9],S,ans,j,C,t;

int main()
{
	scanf("%d\n",&N);
	for(;N--;)
	{
		for(i=S=C=0;i<9;i++)
		{
			scanf("%x",&A[i]);
			if(i<8)
				S+=A[i];
		}
		if((A[8]&1)!=(S&1))
		{
			t=0;
			ans=1;
			for(j=0;j<8;j++)t+=(A[j]^1)&1;
			C+=t;
		}
		else
		{
			t=0;
			ans=0;
			for(j=0;j<8;j++)
				t+=(A[j]^0)&1;
			C+=t;
		}
		for(i=1;i<32;i++)
		{
			t=0;
			for(j=0;j<8;j++)
				t+=((A[j]^0)>>i)&1;
			if(C>>i&1)
				t++;
			if((t&1)==(((A[8]^0)>>i)&1))
			{
				C+=(t&0xffffffe)<<i;
				continue;
			}
			else
			{
				t=0;
				for(j=0;j<8;j++)
				{
					t+=((A[j]^0xffffffff)>>i)&1;
				}
				if(C>>i&1)
					t++;
				ans+=1<<i;
				C+=(t&0xffffffe)<<i;
			}
		}
		printf("%x\n",ans);
	}
	return 0;
}

Measured memory_bytes: 604
def main():
    n, x = map(int, input().split())
    num_list = [int(input()) for _ in range(n)]

    ans = n

    min_sum = sum(num_list)

    while x - min_sum >= 0:
        x -= min(num_list)
        ans += 1

    print(ans-1)

if __name__ == '__main__':
    main()

Measured memory_bytes: 40300
#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define rrep(i, n) for (int i = 1; i <= n; i++)
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a,b); }
using P = pair <int, int>;
 
ll MOD = 1000000007;
ll INF =1<<29;
 
int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    map<int,int>mp;
    rep(i,n){
        mp[a[i]]++;
    }
    int ans = 0;
    for(auto p :mp){
        int x = p.second;
        if(x%2==1) ans++; 
    }
    cout << ans <<endl;
}

Measured memory_bytes: 5376
#include <cstdio>
#include <iostream>
#include <vector>
#include <list>
#include <cmath>
#include <fstream>
#include <algorithm>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <complex>
#include <iterator>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <stack>
#include <climits>
#include <deque>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
double EPS=1e-10;
double EQ(double a,double b){
  return abs(a-b)<EPS;
}
void fast_stream(){
  cin.tie(0);
  std::ios_base::sync_with_stdio(0);
}
template<class T>
string IntToString(T num){
  string res;stringstream ss;ss<<num;
  return ss.str();
}
ll StringToInt(string &str){
  ll res=0;
  for(int i=0;i<(int)str.size();i++)
    res=(res*10+str[i]-'0');
  return res;
}
int N;
ll M;
ll as[101];
double ps[101];

ll gcd(ll a,ll b){
  if(b==0)return a;
  return gcd(b,a%b);
}
ll lcm(ll a,ll b){
  return a/gcd(a,b)*b;
}
long double lcm2(ll a,ll b){
  return 1.0*a*b/gcd(a,b);
}

int main(){
  cin>>N>>M;
  for(int i=0;i<N;i++)cin>>as[i];
  for(int i=0;i<N;i++){
    cin>>ps[i];
    ps[i]/=100;
  }
  double res=0;
  for(int i=1;i<(1<<N);i++){
    double per=1;
    int bitCnt=__builtin_popcount(i);
    ll m=1;
    for(int j=0;j<N;j++){
      if((i>>j)&1){
        // Mを超えたらfin
        double d=lcm2(m,as[j]);
        if(lcm2(m,as[j])>M){
          m=M+1;
          break;
        }
        m=lcm(m,as[j]);
        per*=ps[j];
      }
    }
    if(!(bitCnt%2))res-=per*(M/m);
    else res+=per*(M/m);
  }
  printf("%.10f\n",res);
  return 0;
}

Measured memory_bytes: 1260
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n;i>0;i--)
#define rep1(i,s,n) for(int i=s;i<n;i++)
#define max0(a,b,c) max(max(a,b),c)
#define min0(a,b,c) min(min(a,b),c)
#define ft first
#define sc second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define mod 1000000007
using namespace std;
using Graph = vector<vector<int>>;
typedef long long lint;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldouble;
typedef vector<int> vec;
typedef vector<ll> lvec;
typedef vector<ull> ulvec;
typedef vector<pair<int,int>> pvec;
typedef vector<pair<ll,ll>> plvec;
typedef vector<tuple<ll,ll,ll>> tvec;
typedef vector<string> svec;

const ll max_h=300,max_w=300;
ll h,w,k;
char s[max_h+1][max_w+1];
ll a[max_h+1][max_w+1];
bool flag=true;
void solve(){
    ll m=1,p=0,c;
    stack<int> st;
    rep(j,w){
        c=0;
        rep(i,h){
            if(m>k){
                a[i][j]=a[i][j-1];
                c++;
            }
            else if(c>=1&&s[i][j]=='#'){
                m++;
                a[i][j]=m;
                c++;
                if(!flag) a[i][j-1]=m;
            }
            else{
                a[i][j]=m;
                if(s[i][j]=='#') c++;
                if(!flag) a[i][j-1]=a[i][j];
            }
        }
        if(c>0){
            m++;
            flag=true;
        }else{
            m=a[h-1][j];
            flag=false;
            st.push(j);
        }
    }
    int u,v=-3;
    if(!st.empty()){
        u=st.top();st.pop();
    }
    while(!st.empty()){
        v=st.top();st.pop();
        if(u-v==1){
            rep(i,h) a[i][v]=a[i][u];
        }
        u=v;
    }
}

int main(){
    cin>>h>>w>>k;
    rep(i,h){
        rep(j,w) cin>>s[i][j];
    }
    solve();
    rep(i,h){
        rep(j,w) cout<<a[i][j]<<" ";
        cout<<endl;
    }
}

Measured memory_bytes: 1536
#include <iostream> // cout, endl, cin
#include <iomanip>
#include <string>        // string, to_string, stoi
#include <vector>        // vector
#include <algorithm>     // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility>       // pair, make_pair
#include <tuple>         // tuple, make_tuple
#include <cstdint>       // int64_t, int*_t
#include <cstdio>        // printf
#include <map>           // map
#include <queue>         // queue, priority_queue
#include <set>           // set
#include <stack>         // stack
#include <deque>         // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset>        // bitset
#include <cctype>        // isupper, islower, isdigit, toupper, tolower
#include <math.h>
#include <numeric>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
const int INF = 1001001001;

int main()
{
    int N;
    cin >> N;
    vector<pair<int, int>> v(N);
    rep(i, N) cin >> v.at(i).first >> v.at(i).second;

    int ans = 0;
    rep(i, N)
    {
        auto lr = v.at(i);
        ans += lr.second - lr.first + 1;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<algorithm>
#include<iostream>
#include<vector>
#include<string>
#include<map>
#include<stack>
#include<queue>

typedef long long i64;

using namespace std;

int main(){
    int N;
    cin>>N;

    if(N<=999) cout<<"ABC\n";
    else cout<<"ABD\n";
    
}



Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
const long long MOD = 1000000007;

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

    ll a = 0;
    ll bc = 0;
    ll ans = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == 'A') {
            if (bc == 0) {
                a++;
            } else if (bc == 1) {
                a = 1;
                bc = 0;
            } else if (bc == 2) {
                a++;
            }
        } else if (s[i] == 'B') {
            if (bc == 0) {
                bc = 1;
            } else if (bc == 1) {
                a = 0;
                bc = 0;
            } else if (bc == 2) {
                bc = 1;
            }
        } else if (s[i] == 'C') {
            if (bc == 0) {
                a = 0;
            } else if (bc == 1) {
                ans += a;
                bc = 2;
            } else if (bc == 2) {
                a = 0;
                bc = 0;
            }
        }

        //printf("%c (a, bc, ans) = (%d, %d, %d)\n", s[i], a, bc, ans);
    }

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 640
/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

int n, ll[100005], lr[100005], rl[100005], rr[100005];

struct node
{
	int l, r;
	bool operator <(const node &rhs)const{
		return l == rhs.l ? r < rhs.r : l < rhs.l;
	}
}a[100005];

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	scanf("%d", &n);
	for (int i = 1; i <= n; i++){
		scanf("%d %d", &a[i].l, &a[i].r);
	}
	sort(a + 1, a + 1 + n);
	lr[0] = 0x3f3f3f3f, rr[n + 1] = 0x3f3f3f3f;
	for (int i = 1; i <= n; i++) ll[i] = max(ll[i - 1], a[i].l), lr[i] = min(lr[i - 1], a[i].r);
	for (int i = n; i >= 1; i--) rl[i] = max(rl[i + 1], a[i].l), rr[i] = min(rr[i + 1], a[i].r);
	int ans = 0;
	for (int i = 1; i < n; i++) ans = max(ans, max(0, lr[i] - ll[i] + 1) + max(0, rr[i + 1] - rl[i + 1] + 1));
	for (int i = 1; i <= n; i++) ans = max(ans, a[i].r - a[i].l + 1 + max(0, min(lr[i - 1], rr[i + 1]) - max(ll[i - 1], rl[i + 1]) + 1));	
	printf("%d\n", ans);

	return 0;
}
/**/

Measured memory_bytes: 2560
from collections import deque


def search(N, adj, start):
    dist = [-1] * N
    q = deque()
    q.append((start, 0, -1))
    while len(q):
        p, d, prev = q.popleft()
        if dist[p] != -1:
            if dist[p] != d:
                return None
            continue
        dist[p] = d
        for nxt in adj[p]:
            if nxt == prev:
                continue
            if dist[nxt] == -1:
                q.append((nxt, d+1, prev))
    return dist


def main():
    N = int(input())
    S = [input() for _ in range(N)]
    adj = [set() for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if S[i][j] == "1":
                adj[i].add(j)
    start = 0
    dist = search(N, adj, 0)
    if dist == None:
        print(-1)
        return
    ans = 0
    for i in range(N):
        tmp = max(search(N, adj, i)) + 1
        ans = max(ans, tmp)
    print(ans)


if __name__ == "__main__":
    main()


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

int main()
{
    long long w, h, x, y;
    cin >> w >> h >> x >> y;
    
    long long ans;
    if(w%2==1&&h%2==1){
        ans=h*w-1;
        ans/=2;
        cout<<ans+0.5<<endl;
    }
    else{
        ans=h*w/2;
        cout<<ans<<endl;
    }

	if(w%2==1||h%2==1){
        cout<<0<<endl;
    }
    else if (w / 2 == x && h / 2 == y)
    {
        cout << 1 << endl;
    }
    else
    {
        cout << 0 << endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define err(args...) {}
#ifdef DEBUG
#include "_debug.cpp"
#endif
using namespace std;
using ll = long long;
using ld = long double;
template <typename T> using lim = numeric_limits<T>;
template <typename T> istream& operator>>(istream& is, vector<T>& a) { for(T& x : a) { is >> x; } return is; }
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> a(n), b(n), c(n);
    cin >> a >> b >> c;
    for(int& i : a) i--;
    int ans = 0;
    for(int i = 0; i < n; i++) {
        ans += b[a[i]];
        if(i and a[i] - a[i-1] == 1) ans += c[a[i-1]];
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(v) v.begin(),v.end()
#define len(x) (ll)(x).length()
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int INF=1e9;
const ll INFS=1e18;
const int di[] = {-1,0,1,0};
const int dj[] = {0,-1,0,1};
 
int main() {
  string s;
  cin>>s;
  bool ans=false;
  for(int i=0;i<len(s);i++){
    for(int j=i;j<len(s);j++){
      string t=s.substr(0,i)+s.substr(j);
      if(t=="keyence"){
        ans=true;
      }
    }
  }
  cout<<(ans?"YES":"NO")<<endl;
}

Measured memory_bytes: 3640
#include<iostream>
#include<string>
using namespace std;
int main(){
  string str;
  int ab[26]={};
  int i;
  while(getline(cin,str)){
    for(i=0;i<str.size();i++){
      if(str[i]>='a'&&str[i]<='z') ab[str[i]-'a']++;
      else if(str[i]>='A'&&str[i]<='Z') ab[str[i]-'A']++;
    }
  //cout << str << endl;
  }
  for(i=0;i<26;i++){
    cout << (char)('a'+i) << " : " << ab[i] << endl;
  }
  return 0;
}



Measured memory_bytes: 3184
import java.util.Map;
import java.util.Map.Entry;
import java.util.Scanner;
import java.util.TreeMap;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long k = sc.nextLong();
        Map<Integer,Long> map = new TreeMap<>();
        for(int i = 0; i < n; i++) {
            int key = sc.nextInt();
            long value = sc.nextInt();
            if(map.containsKey(key)) {
                map.put(key, map.get(key) + value);
            }else {
                map.put(key, value);
            }
        }
        long sum = 0l;
        for(Entry<Integer, Long> entry : map.entrySet()) {
            sum += entry.getValue();
            if(sum >= k) {
                System.out.println(entry.getKey());
                return;
            }
        }
    }
}

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

int main(){
    ll n,k;
    cin >> n >> k;
    vector<ll> vec(n);
    rep(i,n) cin >> vec[i];
    ll ans = 0;
    sort(vec.begin(),vec.end());
    for(ll i=0;i<n-k;i++){
        ans+=vec[i];
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 1792
N = int(input())
memo = [N]*(N+1)
unit = [1]
for b in [6,9]:
    u = b
    while u <= N:
        unit.append(u)
        u *= b
unit.sort()
cur = set({0})
for i in range(1,N+1):
    prev = cur
    cur = set()
    for p in prev:
        for u in unit:
            c = p + u
            if c == N:
                print(i)
                exit()
            elif c > N:
                break
            elif memo[c] > i:
                cur.add(c)
                memo[c] = i

Measured memory_bytes: 6184
#include <iostream>
#include <iomanip>
#include <fstream>
#include <string>
#include <array>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <bitset>
#include <tuple>
#include <cmath>
#include <complex>
#include <algorithm>
#include <utility>
#include <regex>
#include <cstdint>
#include <numeric>
#include <functional>
#include <cassert>

using namespace std;
using ll = int64_t;
using ull = uint64_t;

constexpr ll INF = 1000000000;/* 1e+9a */

ll calc_dsum(ll X){
    ll sum = 0;
    while(X > 0){
        sum += X % 10;
        X /= 10;
    }
    return sum;
}

void solve(istream &cin) {
    ll N;
    cin >> N;
    if(!cin) return;
    ll ans = INF;
    for (int i = 1; i <= N/2 + 1; ++i) {
        ll as = calc_dsum(i);
        ll bs = calc_dsum(N - i);
        ans = min(ans, as+bs);
    } // end i
    cout << ans << endl;
    
}

int main(int argc, char *argv[]) {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << setprecision(16) << scientific;
#ifdef DEBUG
    cerr << "DEBUG MODE" << endl;
    string test_cases = "test.txt";
    auto fs = fstream(test_cases, fstream::in);
    while(fs) {
        solve(fs);
    }
#else
    solve(cin);
#endif
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int

using namespace std;

const ll mod=1000000007;
const ll inf=LONG_LONG_MAX;
ll dx4[4]={1,0,-1,0};
ll dy4[4]={0,-1,0,1};
ll dx8[8]={1,0,-1,1,-1,1,0,-1};
ll dy8[8]={1,1,1,0,0,-1,-1,-1};

int main(){

    string s;
    ll q;
    cin >> s >> q;
    ll sign=1;
    vector<char> v1,v2;
    for(ll i=0;i<q;i++){
        ll t;
        cin >>t;
        if(t==1)sign*=-1;
        else{
            ll f;
            char c;
            cin >> f >> c;
            if(sign==1){
                if(f==1){
                    v1.push_back(c);
                }
                else{
                    v2.push_back(c);
                }
            }
            else{
                if(f==1){
                    v2.push_back(c);
                }
                else{
                    v1.push_back(c);
                }
            }
        }
    }

    

    if(sign==1){
        for(ll i=v1.size()-1;i>=0;i--)cout << v1[i];
        for(ll i=0;i<s.size();i++)cout << s[i];
        for(ll i=0;i<v2.size();i++)cout << v2[i];
        cout << endl;
    }
    else{
        for(ll i=v2.size()-1;i>=0;i--)cout << v2[i];
        for(ll i=s.size()-1;i>=0;i--)cout << s[i];
        for(ll i=0;i<v1.size();i++)cout << v1[i];
        cout << endl;
    }

}

Measured memory_bytes: 3868
#include<iostream>
#include<cstdio>
#include<sstream>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
#include<cstring>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int N = 1005;
const int inf = 0x3f3f3f3f;
int main()
{
	int a,f=0;
	cin>>a;
	while(a)
	{
		if(a%10==7)f=1;
		a/=10;
	}
	if(f)cout<<"Yes";
	else cout<<"No";
	return 0;
}

Measured memory_bytes: 3632
let n, m = Scanf.scanf " %d %d" @@ fun a b -> a, b
let a_ss = Array.(init n @@ fun _ -> Scanf.scanf " %d" @@ fun k -> init k @@ fun _ -> Scanf.scanf " %d" pred)
let cs = Array.make m 0
let _ = Array.(iter (fun a_s -> iter (fun a -> cs.(a) <- cs.(a) + 1) a_s) a_ss; fold_left (fun a c -> a + if c = n then 1 else 0) 0 cs) |> Printf.printf "%d\n"

Measured memory_bytes: 2432
//メモ化再帰
//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_B&lang=jp
#include<vector>
#include<iostream>
#include<algorithm>
#define MAX_N 101
#define MAX_W 10001

using namespace std;
int n,W;
int w[MAX_N];
int v[MAX_N];
int dp[MAX_N + 1][MAX_W + 1];//メモ化テーブル
//i番目以降の品物から重さの総和がj以下となるように選ぶ
int rec(int i,int j)
{
	if (dp[i][j] >= 0)
	{
		//すでに調べたことがあるならばその結果を再利用
		return dp[i][j];
	}
	int res;
	if (i == n)
	{
		res = 0;
	}
	else if (j < w[i])
	{
		res = rec(i + 1, j);
	}
	else
	{
		res = max(rec(i + 1, j), rec(i + 1, j - w[i]) + v[i]);
	}
	//結果をテーブルに記憶
	return dp[i][j] = res;
}
int main()
{
	cin >> n >> W;
	for (int i = 0; i < n; i++)
	{
		cin >> v[i] >> w[i];
	}
	for (int i = 0; i < MAX_N; i++)
	{
		for (int j = 0; j < MAX_W; j++)
		{
			dp[i][j] = -1;
		}
	}
	cout << rec(0, W) << endl;
}


Measured memory_bytes: 7048
#include<bits/stdc++.h>
#define pb push_back
#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define f first
#define s second
#define int long long
#define sz(x) (ll)(x.size())
using namespace std;


const int mod = 1e9+7;

int expo_pow(int x,int y){
 if(y == 0) return 1;
  y=y%(mod-1);
  x%=mod;
  if(y==0) y=mod-1;
  int res=1;
  while(y){
    if(y&1) res=(res*x)%mod;
    x=(x*x)%mod;
    y>>=1; 
  }
  return res;
}

ll add()
{
    return 0;
}

template <typename T, typename... Types>
T add(T var1, Types... var2){
    return (((((ll)(var1)) % mod + (ll)(add(var2...))) % mod) + mod) % mod;
}

ll mul(){
    return 1;
}

template <typename T, typename... Types>
T mul(T var1, Types... var2){
    return (((ll)(var1)) % mod * (ll)(mul(var2...))) % mod;
}

void solve(){
  int n;
  cin >> n;
  int a[n];
  int b[n];
  for (int i = 0 ;i < n; ++i) cin >> a[i];
  for (int i = 0; i < n; ++i) cin >> b[i];

  int freq_a[n+2] = {0};
  for (int i = 0; i < n; ++i) freq_a[a[i]]++;

  int mx = 0;
  
  int sta = 0;
  int stb = 0;

  for (int i = 1; i <= n; ++i) {
    while (sta < n and a[sta] == i) sta++;
    mx = max(sta - stb,mx);
    while (stb < n and b[stb] == i) stb++;
  }

  vector<int> ans(n);
  for (int i = mx; i < n; i++) ans[i] = b[i-mx];
  for (int i = 0 ; i < mx; ++i) ans[i] = b[n-mx + i];
  
  int fl = 0;
  for (int i = 0; i < n; ++i) {
    if (a[i] == ans[i]) fl = 1;
  }

  if (fl ==1 ) cout << "No\n";
  else {
    cout << "Yes\n";
    for (auto u:ans) cout << u << " ";
    cout << "\n";
  }

}


signed main(){
  fast;
  int test = 1;
  int i=1;
  while(test--){
    solve();
  }
}






Measured memory_bytes: 9524
#include "bits/stdc++.h"
#define ll long long
#define ALL(x) x.begin(),x.end()
#define MOD 1000000007
using namespace std;

int main(){
  ll N;
  cin>>N;
  vector<ll> a(N);
  vector<ll> b(N);
  vector<ll> c(N-1);


  for(ll i=0;i<N;i++){
    cin>>a[i];
  }
  for(ll i=0;i<N;i++){
    cin>>b[i];
  }
  for(ll i=0;i<N-1;i++){
    cin>>c[i];
  }

  ll ans =0;

for(ll i=0;i<N;i++){
  ans+=b[a[i]-1];
}

//cout<<ans<<endl;

for(ll i=0;i<N-1;i++){
  if(a[i]+1==a[i+1]){
    ans+=c[a[i]-1];
  }
}

cout<<ans<<endl;

}

Measured memory_bytes: 256
n, k = map(int, input().split())
A = list(map(int,input().split()))
original_k = k

seen = set([0])
cur = 0
visited = [0]
for _ in range(n):
    next_ = A[cur] - 1
    if next_ in seen:
        i = visited.index(next_)
        visited = visited[i:]
        break
    else:
        seen.add(next_)
        visited.append(next_)
    if len(visited) - 1 == original_k:
        print(visited[-1]+1)
        exit()
    cur = next_
    k -= 1
   


index = k % len(visited)
print(visited[k%len(visited)-1]+1)

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

int main() {
	int X, t;
	cin >> X >> t;
	cout << max(0, X - t);
	return 0;
}
/*
31536000のコメント解説欄
ここテンプレで用意してるから、A問題とかだとこの先空欄の危険あり

要するに、0かX-tが答えとなる
X-t>=0の時出力はX-t、X-t<0なら0を出力するので、どちらか大きい方を出力すれば良い
*/

Measured memory_bytes: 256
process.stdin.resume();
process.stdin.setEncoding('utf8');

var lines = [];
var reader = require('readline').createInterface({
  input: process.stdin,
  output: process.stdout
});
reader.on('line', (line) => {
  lines.push(line);
});
reader.on('close', () => {
    const [a,b] = lines[0].split(" ").map(v=>v-0);
    let ans = 0;
    for(let i=a;i<=b;i++){
        ans += check(i);
    }
    console.log(ans);
});

check = (a)=>{
    return a.toString()===a.toString().split("").reverse().join("")?1:0;
}


Measured memory_bytes: 37664
#include<stdio.h>
int main(){
  int A[3];
  for(int i = 0;i < 3;i++){
    scanf("%d",&A[i]);
  }
  for(int i = 0;i < 2;i++){
    for(int j = 0;j < 2;j++){
      if(A[j] < A[j + 1]){
        int t = A[j];
        A[j] = A[j + 1];
        A[j + 1] = t;
      }
    }
  }
  printf("%d",A[0] - A[2]);
  return 0;
}

Measured memory_bytes: 128
# ITP1_7_B.py
while True:
    ans = 0
    N, X = map(int,input().split())
    if N==0 and X == 0:
        break
    for i in range(1,N+1):
        for j in range(i+1,N):
            k = X - i - j
            if k > i and k > j and N >= k > 0:
                ans+=1
    print(ans)


Measured memory_bytes: 5592
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=100001,INF=1<<30;
int V,cmp[MAX];
vector<int> G[MAX],rG[MAX],vs;
bool used[MAX];

void add_edge(int from,int to){
    G[from].push_back(to);
    rG[to].push_back(from);
}

void DFS(int v){
    used[v]=1;
    for(int i=0;i<G[v].size();i++){
        if(used[G[v][i]]==0) DFS(G[v][i]);
    }
    vs.push_back(v);
}

void rDFS(int v,int k){
    used[v]=1;
    cmp[v]=k;
    for(int i=0;i<rG[v].size();i++){
        if(used[rG[v][i]]==0) rDFS(rG[v][i],k);
    }
}

int scc(){
    memset(used,0,sizeof(used));
    vs.clear();
    for(int v=0;v<V;v++){
        if(used[v]==0) DFS(v);
    }
    
    memset(used,0,sizeof(used));
    int k=0;
    for(int i=vs.size()-1;i>=0;i--){
        if(used[vs[i]]==0) rDFS(vs[i],k++);
    }
    return k;
}

int main(){

    int E;cin>>V>>E;
    for(int i=0;i<E;i++){
        int a,b;cin>>a>>b;
        add_edge(a,b);
    }
    
    scc();
    
    for(int i=vs.size()-1;i>=0;i--){
        cout<<vs[i]<<endl;
    }
    
    
    
}




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

void prians(bool answer) {
  if(answer)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}

int a, b, c;

int main() {
  cin >> a >> b >> c;
  prians(c >= a && c <= b);
  return 0;
}

Measured memory_bytes: 256
use std::io::*;
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let a: String = read();
    let b: String = read();
    let ac: Vec<char> = a.chars().collect();
    let bc: Vec<char> = b.chars().collect();
    let mut done = false;

    if ac.len() > bc.len() {
        println!("GREATER");
        done = true;
    }

    if bc.len() > ac.len() {
        println!("LESS");
        done = true;
    }
    if done {
        return;
    }

    for i in 0..ac.len() {
        let ai = ac[i].to_digit(10).unwrap();
        let bi = bc[i].to_digit(10).unwrap();
        if ai > bi {
            println!("GREATER");
            done = true;
            break;
        }

        if bi > ai {
            println!("LESS");
            done = true;
            break;
        }
    }
    if !done {
        println!("EQUAL")
    }
}


Measured memory_bytes: 4352
#include <stdio.h>

int main(void) {
  // input
  int a;
  char s[10];
  scanf("%d", &a);
  scanf("%s", s);

  // output
  if (a >= 3200) {
    printf("%s", s);
  } else {
    printf("red");
  }

  return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define vec(k) vector<k>
#define vecvec(k) vector<vector<k> >
#define pai(k) pair<k,k>
#define mod 1000000007
#define mpai make_pair
#define p1 first
#define p2 second
#define umap(x,y) unordered_map<x,y>

class graph
{public:
	int v;
	map<int, vector<int >>adj;

	graph(int x)
		{v=x;
			for(int i=0;i<v;i++)
				adj.insert(make_pair(1,vector<int>()));
		}

	void addedge(int u, int v)
	{
		adj[u].push_back(v);
	}
	int solve()
	{
		int dist[v+1]={0};
		int indegree[v+1]={0};
		memset(dist,0,sizeof(dist));
		memset(indegree,0,sizeof(indegree));
		queue<int >q;
		int temp, maxans=0;

		for(int i=1;i<=v;i++)
		{
			for(auto child:adj[i])
				indegree[child]+=1;
		}
		for(int i=1;i<=v;i++)
			if(indegree[i]==0)
				q.push(i);

		while(!q.empty())
		{
			temp=q.front();
			q.pop();

			for(auto child :adj[temp])
			{
				if(dist[child] < dist[temp]+1)
				{
					dist[child]=dist[temp]+1;
					q.push(child);
				}
			}
		}
		for(int i=1;i<=v;i++)
			{
				// cout<<dist[i]<<" ";
			maxans=max(maxans,dist[i]);
		}

		return maxans;

	}

	void dfs(int node, bool *visited, int *dp)
	{
		visited[node]=true;

		for(auto i:adj[node])
		{
			if(!visited[i])
				dfs(i,visited, dp);

			dp[node]=max(dp[node], dp[i]+1);
		}
	}
	int solvedfs()
	{
		bool visited[v+1];
		memset(visited,false,sizeof(visited));
		int dp[v+1];
		memset(dp,0,sizeof(dp));

		for(int i=1;i<=v;i++)
		{
			if(!visited[i])
				dfs(i,visited,dp);
		}
		int maxans=0;

		for(int i=1;i<=v;i++)
		{
			maxans=max(maxans,dp[i]);
		}
		return maxans;
	}

};

int main()
{
ios_base:: sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);


  int m,n,a,b;
  cin>>n>>m;
  graph g(n);
  for(int i=0;i<m;i++)
  {
  	cin>>a>>b;
  	g.addedge(a,b);
  }
  int ans=g.solvedfs();
  cout<<ans<<"\n";

return 0;
}


Measured memory_bytes: 13312
package main

import (
	"bufio"
	"os"
	"strconv"
)

const NUM int = 1e9 + 7

var C [][]int

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)

	sc.Scan()
	N, _ := strconv.Atoi(sc.Text())

	sc.Scan()
	K, _ := strconv.Atoi(sc.Text())

	C = make([][]int, N+1)
	for i := 0; i < N+1; i++ {
		C[i] = make([]int, i+2)
		C[i][0] = 1
		for j := 1; j <= i; j++ {
			C[i][j] = (C[i-1][j-1] + C[i-1][j]) % NUM
		}
	}

	out := bufio.NewWriter(os.Stdout)
	for i := 1; i <= K; i++ {
		result := comb(N-K+1, i) * comb(K-1, i-1) % NUM
		out.WriteString(strconv.Itoa(result) + "\n")
	}
	out.Flush()
}

func comb(n, m int) int {
	if n < m {
		return 0
	}
	return C[n][m]
}


Measured memory_bytes: 18432
import std.stdio, std.conv, std.string, std.array, std.range, std.algorithm, std.container;
import std.math, std.random, std.bigint, std.datetime, std.format;
void main(string[] args){ if(args.length > 1) if(args[1] == "-debug") DEBUG = 1; solve(); } bool DEBUG = 0; 
void log(A ...)(lazy A a){ if(DEBUG) print(a); }
void print(){ writeln(""); } void print(T)(T t){ writeln(t); } void print(T, A ...)(T t, A a){ write(t, " "), print(a); }
string unsplit(T)(T xs){ return xs.array.to!(string[]).join(" "); }
string scan(){ static string[] ss; while(!ss.length) ss = readln.chomp.split; string res = ss[0]; ss.popFront; return res; }
T scan(T)(){ return scan.to!T; } T[] scan(T)(int n){ return n.iota.map!(i => scan!T()).array; }
T lowerTo(T)(ref T x, T y){ if(x > y) x = y; return x; } T raiseTo(T)(ref T x, T y){ if(x < y) x = y; return x; }

// ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- //

void solve(){
  int n = scan!int;
  long[] as = scan!long(n);
  
  long b = 0;
  long ans = 0;
  foreach(a; as){
    if(b > a) ans += b - a;
    b.raiseTo(a);
  }
  
  ans.writeln;
  
}

Measured memory_bytes: 10740
from fractions import gcd
def main():
    n, m = list(map(int, input().split()))
    s = list(input())
    t = list(input())
    lcm = n * m // gcd(n, m)
    a, b = lcm // n, lcm // m
    lcmx = a * b // gcd(a, b)
    for i in range(lcm // lcmx):
        if s[i * b] != t[i * a]:
            print(-1)
            break
    else:
        print(lcm)

if __name__ == '__main__':
    main()


Measured memory_bytes: 77804
//ヘッダー
#include<bits/stdc++.h>
using namespace std;

//型定義
typedef long long ll;

//定数
#define INF 1000000000 //10^9:極めて大きい値,∞
#define MOD 1e+9+7 //10^9+7
#define MAXR 100000 //10^5:配列の最大のrange(素数列挙などで使用)

//REPマクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define REP2(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define REPD2(i,a,b) for(ll i=a;i>=(ll)(b);i--)

//vectorの扱い
#define ALL(x) (x).begin(),(x).end() //sortなどの引数省略
#define SIZE(x) ((ll)(x).size()) //size
#define MAX(x) *max_element(ALL(x)) //最大値
#define MIN(x) *min_element(ALL(x)) //最小値

//グローバル変数


//ライブラリ挿入
int main(){
    int N,Q;
    string S;
    cin >> N;
    cin >> S;
    int alphabet;
    vector<set<int>> a(26,{INF});
    REP(i,N){
        alphabet=S[i]-'a';
        a[alphabet].insert(i);
    }

    int ans;
    cin >> Q;
    int t,num,l,r;
    char c;
    REP(i,Q){
        cin >> t;
        if(t==1){
            cin >> num >> c;
            num--;
            alphabet=S[num]-'a';
            a[alphabet].erase(num);
            alphabet=c-'a';
            S[num]=c;
            a[alphabet].insert(num);
        }else{
            cin >> l >> r;
            l--;
            ans=0;
            REP(j,26){
                int lid = *a[j].lower_bound(l);
                int rid = *a[j].lower_bound(r);
                if(rid>lid) ans++;
            }
            cout << ans << endl;
        }

    }
    


}

Measured memory_bytes: 24196
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		Task solver = new Task();
		solver.solve(1, in, out);
		out.close();

	}
	static class Task{
		public void solve(int testNumber, InputReader in, PrintWriter out) {
			int n = in.nextInt(), m = in.nextInt();
			int se = 100002, fi = 0;
			for(int t = -1; ++t < m;) {
				fi = Math.max(fi, in.nextInt());
				se = Math.min(se, in.nextInt());
				
			}
			out.print(Math.max(0, se-fi+1));
		}//Solve
	}//task
	
	
	static class InputReader{
		public BufferedReader reader;
		public StringTokenizer tokenizer;
		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream), 32768);
			tokenizer = null;
		}
		public String next() {
			while(tokenizer == null || ! tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}
		public int nextInt() {
			return Integer.parseInt(next());
		}
		public int[] nextIntArray(int n) {
			int[] a = new int[n];
			for(int i = -1; ++i < n;) a[i] = nextInt();
			return a;
		}
		public long nextLong() {
			return Long.parseLong(next());
		}
	}
}


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


int main() {
    string s;
    cin >> s;
    int n = s.size();
    
    //cout << s[0];
    for (int i = 0;i < n; i++) {
        if (i % 2 == 0) cout << s[i];
    }
    cout << endl;
    return 0;
}

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

int main(){
  double l;
  cin >> l;
  double s = l/3;
  printf("%.9lf\n",s*s*s);
  
  return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
using namespace std;
int H,W;
int A[200];
int dp[200][200];
main()
{
	scanf("%d%d",&H,&W);
	for(int i=0;i<W;i++)for(int j=0;j<W;j++)dp[i][j]=-1e9;
	dp[0][1]=0;
	for(int _=0;_<H;_++)
	{
		for(int i=0;i<W;i++)scanf("%d",&A[i]);
		for(int i=0;i<W;i++)for(int j=i+1;j<W;j++)
		{
			dp[i][j]+=A[i];
			if(i+1<j)dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
		}
		for(int i=0;i<W;i++)for(int j=i+1;j<W;j++)
		{
			dp[i][j]+=A[j];
			if(j+1<W)dp[i][j+1]=max(dp[i][j+1],dp[i][j]);
		}
	}
	int ans=0;
	for(int i=0;i+1<W;i++)ans=max(ans,dp[i][W-1]);
	printf("%d\n",ans);
}

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

int main(){
	while(1){
		int n, h, m;
		string str, c;
		
		cin>>str;

		if (str == "-") break;
	
		cin>>m;
		
		for(int i = 0; i < m; i++){
			cin>>h;

			c = str;
			str = ""; 
			

			for(int j = h; j < (int) c.size(); j++) {
				str += c[j];
			}
			for(int j = 0; j < h; j++){
				str += c[j];
			}
		}
	
		cout<<str<<endl;

	}

	return 0;
}


Measured memory_bytes: 3140
#include <stdlib.h>
#include <stdio.h>
#define SENTINEL -1
typedef struct { int id, parent, left, right; } node;

static void preorder(const node *nodes, int id) {
  if (id == SENTINEL) return;
  printf(" %d", id);
  preorder(nodes, nodes[id].left);
  preorder(nodes, nodes[id].right);
}

static void inorder(const node *nodes, int id) {
  if (id == SENTINEL) return;
  inorder(nodes, nodes[id].left);
  printf(" %d", id);
  inorder(nodes, nodes[id].right);
}

static void postorder(const node *nodes, int id) {
  if (id == SENTINEL) return;
  postorder(nodes, nodes[id].left);
  postorder(nodes, nodes[id].right);
  printf(" %d", id);
}

int main(int argc, char **argv) {
  int n, i, id, root;
  node *nodes;

  scanf("%d", &n);
  nodes = (node *) malloc(sizeof(node) * n);
  for (i = 0; i < n; ++i) {
    nodes[i].id = nodes[i].parent = nodes[i].left = nodes[i].right = SENTINEL;
  }
  for (i = 0; i < n; ++i) {
    scanf("%d", &id);
    nodes[id].id = id;
    scanf("%d %d", &nodes[id].left, &nodes[id].right);
    nodes[nodes[id].left].parent = nodes[nodes[id].right].parent = id;
  }
  for (i = 0; i < n; ++i) {
    if (nodes[i].parent == SENTINEL) {
      root = i; break;
    }
  }
  printf("Preorder\n");  preorder(nodes, root);  printf("\n");
  printf("Inorder\n");   inorder(nodes, root);   printf("\n");
  printf("Postorder\n"); postorder(nodes, root); printf("\n");
  free(nodes);
  exit(0);
}


Measured memory_bytes: 2108
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

S = input()
if S[0] == S[1] == S[2] == "R":
    print(3)
elif S[0:2] == "RR" or S[1:3] == "RR":
    print(2)
elif "R" in S:
    print(1)
else:
    print(0)

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

using namespace std;
typedef long long int ll;
typedef pair<int, int> ii;
#define DEBUG freopen("in.txt", "r", stdin);

struct fastio {
    fastio() {
        ios::sync_with_stdio(false);
        cout << setprecision(10) << fixed;
        cin.tie(0);
    }
};

fastio _fast_io;

const int N = 105;
int n, ans;
int a[2][N];

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[0][i];
        if (i > 0)
            a[0][i] += a[0][i - 1];
    }
    for (int i = 0; i < n; ++i) {
        cin >> a[1][i];
        if (i > 0)
            a[1][i] += max(a[1][i - 1], a[0][i]);
        else
            a[1][i] += a[0][i];
    }
    cout << a[1][n - 1] << endl;
    return 0;
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
#define N 100005
using namespace std;
int a[N],dp[N];
int main(){
    int n,x,i,k,j;
    cin>>n>>k;
    for(i=1; i<=n; ++i)
        cin>>a[i];
    for(i=2; i<=n; ++i){
        dp[i]=INT_MAX;
        for(j=1; j<=k && i-j>=1; ++j)
            dp[i]=min(dp[i], dp[i-j]+abs(a[i]-a[i-j]));
    }
    cout<<dp[n];
    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr long long MOD = 1000000007;
constexpr long long INF = 1LL << 60;
const long double PI = acosl(-1.0);
constexpr long double EPS = 1e-11;
template<class T> inline bool chmin(T& a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
template<class T> inline bool chmax(T& a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}
int main(){
ll n;
cin >> n;
vector<ll> a(n), b(n),d(n);
ll cnt = 0;
ll ans = 0;
bool flag = true;
for (ll i = 0; i < n; i++) cin >> a[i];
for (ll i = 0; i < n; i++) cin >> b[i];
for (ll i = 0; i < n; i++) {
    d[i] = a[i] - b[i];
    if (d[i] < 0) {
        cnt += -d[i];
        ans++;
        flag = false;
    }
}
if(flag){
    cout << 0 << endl;
    return 0;
}

sort(d.begin(), d.end(), greater<ll>());
ll i = 0;
while (cnt > 0 and i<n) {
    cnt -= d[i];
    ans++;
    i++;
}
if(cnt>0){
    cout << -1 << endl;
}
else{
    cout << ans << endl;
}
}

Measured memory_bytes: 5628
#include <cstdio>
using namespace std;

int main(){
	double xa1, ya1, xa2, ya2, xb1, yb1, xb2, yb2;
	
	while((scanf("%lf%lf%lf%lf%lf%lf%lf%lf", &xa1, &ya1, &xa2, &ya2, &xb1, &yb1, &xb2, &yb2)) != EOF){
		if(xa2 < xb1 || xb2 < xa1 || ya2 < yb1 || yb2 < ya1){
			printf("NO\n");
		}
		else printf("YES\n");
	}
	
	return 0;
}

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

int main(){
    int H, W;
    cin >> H >> W;    
    vector<string> a;
    for(int i=0; i<H; i++){
        string s;
        cin >> s;
        for(int j=0; j<W; j++){
            if(s[j]=='#'){
                a.push_back(s);
                break;
            }
        }
    }
    H = a.size();
    for(int i=W-1; i>=0; i--){
        bool dup = true;
        for(int j=0; j<H; j++){
            if(a[j][i]=='#') {
                dup = false;
                break;
            }
        }
        if(!dup) continue;
        for(int j=0; j<H; j++){
            a[j].erase(a[j].begin()+i);
        }
    }

    for(int i=0; i<H; i++){
        cout << a[i] << endl;
    }
}


Measured memory_bytes: 256
using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
class Program
{
    static void Main()
    {
        //入力
        //int n = 100;
        /*
        long n = long.Parse(Console.ReadLine());
        long[] input = new long[5];
        for(int a = 0; a < 5; a++)
        {
            input[a]=long.Parse(Console.ReadLine());
        }
        */
        int[] g1 = {1,3,5,7,8,10,12 };
        int[] g2 = { 4,6,9,11};
        int[] g3 = { 2};
        int[] input = Console.ReadLine().Split().Select(i =>int.Parse(i)).ToArray();

        Console.WriteLine((Array.IndexOf(g1,input[0])>-1&& Array.IndexOf(g1, input[1])>-1)|| (Array.IndexOf(g2, input[0])>-1 && Array.IndexOf(g2, input[1])>-1) ?"Yes":"No");

        /*
        //処理速度計測
        var sw = new System.Diagnostics.Stopwatch();
        sw.Start();
        //解法

        //処理速度表示
        sw.Stop();
        TimeSpan ts = sw.Elapsed;
        Console.WriteLine((int)(Math.Floor((ts).TotalMilliseconds))+"ms");
        */
        Console.ReadLine();
        
    }
}

Measured memory_bytes: 13280
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    long a = sc.nextLong();
    long b = sc.nextLong();
    long x = sc.nextLong();
    long ax = 0;
    if (a > 0) {
      ax = ((a - 1) / x) + 1;
    }
    long bx = (b / x) + 1;
    System.out.println(bx - ax);
  }
}

Measured memory_bytes: 24020
from collections import defaultdict, deque
inf = float('inf')

def solve(graph, n, start_node, end_node):
  if start_node == end_node:
    return 0

  global costs_dict
  key = str(start_node) + '-' + str(end_node)
  if key in costs_dict:
    return costs_dict[key][end_node]

  costs = [inf for _ in range(n)]
  costs[start_node] = 0
  flgs = [False for _ in range(n)]

  while not all(flgs):
    prv_node = _get_min_idx(flgs,costs)
    flgs[prv_node] = True

    for node, dis in graph[prv_node]:
      if costs[node] > costs[prv_node] + dis:
        costs[node] = costs[prv_node] + dis
  costs_dict[key] = costs  
  return costs[end_node]
    
    
def _get_min_idx(flgs, costs):
    min_cost = inf
    min_idx = None
    cnt = 0
    for cost, flg in zip(costs, flgs):
      if min_cost > cost and flg is False:
        min_cost = cost
        min_idx = cnt
      cnt += 1
    return min_idx
        

n =int(input())
graph = defaultdict(list)
costs_dict = {}

for _ in range(n-1):
  a,b,c = map(int, input().split())
  graph[a-1].append([b-1,c])
  graph[b-1].append([a-1,c])

q, k = map(int, input().split())
k -= 1

l = [0 for _ in range(n)]
queue = deque()
queue.append(k)
while len(queue) > 0:
  a = queue.pop()
  for b, c in graph[a]:
    if l[b] == 0:
      l[b] = l[a] + c
      queue.append(b)

for _ in range(q):
  x, y = map(int, input().split())
  print( l[x-1] + l[y-1])

Measured memory_bytes: 103832
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<cstdio>
#include<sstream>
#include<iomanip>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef pair<int,pii> pip;
typedef vector<pip>vip;
const double PI=acos(-1);
const double EPS=1e-8;
const double inf=1e8;
int main(){
	int n;
	cin>>n;
	string s="";
	rep(i,n){
		char c;cin>>c;
		s+=c;
	}
	int out=0;
	while(1){
		string t=to_string(out);
		if(s.find(t)!=string::npos)out++;
		else{
			cout<<out<<endl;
			return 0;
		}
	}
}

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

// エイリアス
using  ll = long signed long;
using ull = long unsigned long;
using  ld = long double;
using   P = pair<int, int>;
using llP = pair<ll, ll>;
using DoP = pair<double, double>;

// 汎用マクロ
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define FOREACH(i,q) for (auto &i : q)
#define UNIQUE(v) do { sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end()); } while (false)
#define SZ(x) ((int)(x).size())
template <class T>inline bool chmin(T &a, const T b) {if (a > b) { a = b; return true;} return false;}
template <class T>inline bool chmax(T &a, const T b) {if (a < b) { a = b; return true;} return false;}
template <class T>inline void line_out(const vector<T> vec) {int n = SZ(vec); rep(i, n) { cout << vec[i]; if(i < n-1) cout << " ";}cout << endl;}
const int di[] = {0, 1, 0, -1, 1, 1, -1, -1};
const int dj[] = {1, 0, -1, 0, 1, -1, 1, -1};
const int INF = 1 << 28;
const ll INF64 = 1ll << 55;
const int mod = 1000000007;
//const int mod = 998244353;
struct mint
{
  ll x; // typedef long long ll;
  mint(ll x = 0) : x((x % mod + mod) % mod) {}
  mint operator-() const { return mint(-x); }
  mint &operator+=(const mint a)
  {
    if ((x += a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator-=(const mint a)
  {
    if ((x += mod - a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator*=(const mint a)
  {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const
  {
    mint res(*this);
    return res += a;
  }
  mint operator-(const mint a) const
  {
    mint res(*this);
    return res -= a;
  }
  mint &operator++()
  {
    if ((x += 1) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator--()
  {
    if ((x += mod - 1) >= mod)
      x -= mod;
    return *this;
  }
  mint operator*(const mint a) const
  {
    mint res(*this);
    return res *= a;
  }
  mint pow(ll t) const
  {
    if (!t)
      return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1)
      a *= *this;
    return a;
  }
 
  // for prime mod
  mint inv() const
  {
    return pow(mod - 2);
  }
  mint &operator/=(const mint a)
  {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const
  {
    mint res(*this);
    return res /= a;
  }
};


int main()
{
  int n; cin >> n;
  vector<mint> a(n+1, 0);
  rep(i, n) {
    int x; cin >> x;
    a[i+1] = x;
  }
  rep(i, n) a[i+1] += a[i];
  mint ans = 0;
  for(int i = 1; i <= n; ++i) {
    ans += (a[i]-a[i-1])*(a[n]-a[i]);
  }
  cout << ans.x << endl;
}

Measured memory_bytes: 4784