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

#define lint long long
#define P pair<int, int>
#define LLP pair<long long, long long>
#define REP(i, x, n) for(int i = (x), i##_len = (int)(n) ; i < i##_len ; ++i)
#define rep(i, n) for(int i = 0, i##_len = (int)(n) ; i < i##_len ; ++i)
#define repr(i, n) for(int i = (int)(n) - 1 ; i >= 0 ; --i)
#define SORT(x) sort((x).begin(), (x).end())
#define SORT_INV(x) sort((x).rbegin(), (x).rend())

const int IINF = 1e9 + 10;
const long long LLINF = (long long)1e18 + 10;
const long long MOD = (long long)1e9 + 7;
const int dx4[] = {1, 0, -1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dy8[] = {0, -1, -1, -1, 0, 1, 1, 1};
const double EPS = 1e-8;

int n;
lint k;
vector<lint> a, cnt(50);
lint memo[50][2];

lint solve(int d, bool flag){
    if(d == -1){
        return 0LL;
    }
    if(memo[d][flag] >= 0LL){
        return memo[d][flag];
    }

    lint res = 0, t = 1LL << d;
    if(flag){
        res = t * max(cnt[d], n - cnt[d]);
        res += solve(d - 1, true);
    }else if(k >> d & 1LL){
        res = max(t * cnt[d] + solve(d - 1, true), t * (n - cnt[d]) + solve(d - 1, false));
    }else{
        res = t * cnt[d] + solve(d - 1, false);
    }

    return memo[d][flag] = res;
}

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

    cin >> n >> k;

    a.resize(n);
    rep(i, n){
        cin >> a[i];
    }

    rep(i, n){
        rep(j, 50){
            if(a[i] >> j & 1LL){
                ++cnt[j];
            }
        }
    }

    fill(memo[0], memo[50], -1);

    lint ans = solve(49, false);
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 1024
def star(x):
    return x*(x-1)//2

def root(x):
    compress_node = []
    while parent_list[x] != x:
        compress_node.append(x)
        x = parent_list[x]   
    for i in compress_node:
        parent_list[i] = x
    return x


n, m = [ int(v) for v in input().split() ]
bridge_list = [ [ int(v)-1 for v in input().split() ] for i in range(m) ]
bridge_list.reverse()
parent_list = [ i for i in range(n) ]
connect_list = [ 1 for i in range(n) ]
total_inconvinience = star(n)
ans_list = [total_inconvinience]

for i in bridge_list:
    a, b = i
    ra, rb = root(a), root(b)
    if ra != rb:
        parent_list[ra] = rb
        rc = connect_list[rb]
        connect_list[rb] += connect_list[ra]
        total_inconvinience -= star(connect_list[rb]) - star(connect_list[ra]) - star(rc)
        connect_list[ra] = 0
    ans_list.append(total_inconvinience)

ans_list = ans_list[:-1]
ans_list.reverse()
for i in ans_list:
    print(i)


Measured memory_bytes: 78040
#include<iostream>
#include<string>
using namespace std;
int N,Q;
long long l[100000];
long long r[100000];
int memo[100000] = {};
int main(){
  string S;
  long long counter=0;
  cin >> N >> Q;
  cin >> S;
  for(long long i = 0; i < N-1; i++){
    if((S[i] == 'A') && (S[i+1] == 'C')){
      memo[i+1] = memo[i]+1;
    }else{
      memo[i+1] = memo[i];
    }
  }
  for(long long i = 0; i < Q; i++){
    cin >> l[i] >> r[i];
    counter = memo[r[i]-1] - memo[l[i]-1];
    cout << counter << endl;
  }
  return 0;
}

Measured memory_bytes: 3072
#include<vector>
#include<stdio.h>
using namespace std;
typedef vector<vector<long long>> Mat;
int n,m,l;
void proc(Mat& a,Mat& b){
  Mat res(n,vector<long long>(l));
  for(int i=0;i<n;++i){
    for(int j=0;j<l;++j){
      for(int k=0;k<m;++k){
        res[i][j]+=a[i][k]*b[k][j];
      }
    }
  }
  
  for(int i=0;i<n;++i){
    for(int j=0;j<l-1;++j){
      printf("%lld ",res[i][j]);
    }
    printf("%lld\n",res[i][l-1]);
  }
}
int main(){
  scanf("%d%d%d",&n,&m,&l);
  Mat a(n,vector<long long>(m));
  Mat b(m,vector<long long>(l));
  for(int i=0;i<n;++i)
    for(int j=0;j<m;++j)
      scanf("%d",&a[i][j]);
  for(int i=0;i<m;++i)
    for(int j=0;j<l;++j)
      scanf("%d",&b[i][j]);
      
  proc(a,b);
  return 0;
}

Measured memory_bytes: 1264
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define rep1(i,n) for(int i=1;i<=(int)n;i++)
#define sp(n) cout << fixed << setprecision(n)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
typedef long long ll;
using namespace std;
int main(void){
    ll n;cin>>n;
    vector<ll> a(n);
    rep(i,n) cin>>a[i];
    sort(a.begin(),a.end());
    int l=1,r=n-1;
    ll left=a[0],right=a[0];
    ll res=0,res2=0;
    while(true){
        res+=abs(left-a[r]);
        left=a[r];
        if(l==r)break;
        r--;
        res+=abs(right-a[r]);
        right=a[r];
        if(l==r)break;
        r--;
        res+=abs(left-a[l]);
        left=a[l];
        if(l==r)break;
        l++;
        res+=abs(right-a[l]);
        right=a[l];
        if(l==r)break;
        l++;
    }
    reverse(a.begin(),a.end());
    l=1,r=n-1;
    left=a[0],right=a[0];
    while(true){
        res2+=abs(left-a[r]);
        left=a[r];
        if(l==r)break;
        r--;
        res2+=abs(right-a[r]);
        right=a[r];
        if(l==r)break;
        r--;
        res2+=abs(left-a[l]);
        left=a[l];
        if(l==r)break;
        l++;
        res2+=abs(right-a[l]);
        right=a[l];
        if(l==r)break;
        l++;
    }
    chmax(res,res2);
    cout<<res<<endl;
}

Measured memory_bytes: 4048
#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <map>
#include <set>
#include <math.h>
#include <queue>
#define rep(i,n) for (int i = 0; i < (n); ++i)
typedef long long ll;
using namespace std;

int a[1000001];

int main() {
    int k;
    cin >> k;
    a[1]=7%k;
    for(int i=2; i<=k; ++i) a[i]=(a[i-1]*10+7)%k;
    for(int i=1; i<=k; ++i) {
        if(a[i]==0) {
            cout << i << endl;
            return 0;
        }
    }
    cout << "-1" << endl;
}

Measured memory_bytes: 7044
class SegmentTreeMax:
    def __init__(self, a):
        self.padding =  -float('inf')
        
        n = len(a)
        self.N = 2 ** (n-1).bit_length()
        self.data = [self.padding]*(self.N-1) + a + [self.padding]*(self.N-n)
        for i in range(2*self.N-2, 0, -2):
            self.data[(i-1)//2] = max(self.data[i], self.data[i-1])
    
    def update(self, idx, x):
        idx = self.N - 1 + idx
        self.data[idx] = x
        while idx:
            idx = (idx-1) // 2
            self.data[idx] = max(self.data[2*idx+1], self.data[2*idx+2])
    
    def search(self, i, j):
        # [i, j)の区間の最小値を求める
        idx1 = self.N-1+i
        idx2 = self.N-1+j-1
        result = self.padding
        while idx1 + 1 < idx2:
            if idx1&1 == 0: # idx1が偶数
                result = max(result, self.data[idx1])
            if idx2&1 == 1: # idx2が奇数
                result = max(result, self.data[idx2])
                idx2 -= 1
            
            idx1 //= 2
            idx2 = (idx2 - 1)//2
        
        if idx1 == idx2:
            result = max(result, self.data[idx1])
        else: # idx1 + 1 == idx2
            result = max(result, self.data[idx1], self.data[idx2])
        
        return result


N = int(input())
H = list(map(int, input().split()))
A = list(map(int, input().split()))

dp = [0] * (N+1)
st = SegmentTreeMax(dp)

ans = 0
for h, a in zip(H, A):
  M = st.search(0, h)
  st.update(h, M + a)

print(st.search(0, N+1))

Measured memory_bytes: 121680
from itertools import permutations as P
from math import sqrt as r

N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]
ans_sum = 0
town = list(P(list(range(N)), N))
Q = len(town)

for town in town:
    d = 0
    for i in range(N - 1):
        X = xy[town[i]][0] - xy[town[i + 1]][0]
        Y = xy[town[i]][1] - xy[town[i + 1]][1]
        d += r(X**2 + Y**2)
    #print(d)
    ans_sum += d

print(ans_sum/Q)

Measured memory_bytes: 13916
#include<bits/stdc++.h>
using namespace std;
int main () {
  int a[4];
  string key = "0123456789";
  for (int i = 0; i < 4; i ++) {
    char c;
    cin >> c;
    for (int j = 0; j < 10; j ++) {
      if (c == key[j]) a[i] = j;
    }
  }
  for (int i = 0; i < 8; i ++) {
    int i_ = i;
    char c[3];
    int as_ = a[0];
    for (int j = 0; j < 3; j ++) {
      if (i_ % 2) {
        c[j] = '+';
        as_ += a[j + 1];
      }
      else {
        c[j] = '-';
        as_ -= a[j + 1];
      }
      i_ /= 2;
    }
    if (as_ == 7) {
      for (int j = 0; j < 3; j ++) cout << a[j] << c[j];
      cout << a[3] << "=7" << endl;
      return 0;
    }
  }
}



Measured memory_bytes: 256
import java.math.BigDecimal;
import java.util.*;
import java.util.regex.Pattern;
public class Main {
  public static void main(String[] args){
    new Main().run();
  }
  void run() {
    Scanner sc = new Scanner(System.in);
    BigDecimal A = new BigDecimal(sc.nextDouble());
    BigDecimal B = new BigDecimal(sc.nextDouble());
    String ans = A.multiply(B).toPlainString();
    System.out.println(ans.replaceFirst("\\..*$", ""));
  }
}


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

int main(){
  float min=0;
  float max=0;
  float height=0;

  while(cin >> height){
    if(height==0){
      break;
    }

    if(min == 0){
      min = height;
    }
    else if(min > height){
      min = height;
    }

    if(max < height){
      max = height;
    }

  }

  cout << max-min << endl;

  return 0;
}

Measured memory_bytes: 1280
#include<stdio.h>
 int N,K,i;
 int j=0;
 int hoge[100000];
 
 main(void)
{scanf("%d",&N);
 scanf("%d",&K);
 for(i=1;i<=N;i++){
 scanf("%d",&hoge[i-1]);
 }
 for(i=1;i<=N;i++){
 if(K<=hoge[i-1]){
		j++;
	}
 }	
printf("%d",j);
}	

Measured memory_bytes: 512
#define LOCAL
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include<bits/stdc++.h>
using namespace std;
#define rep(i,x) for(ll i = 0; i < (ll)(x); i++)
#define rrep(i,x) for(ll i = (ll)(x)-1;0 <= i; i--)
#define reps(i,x) for(ll i = 1; i < (ll)(x)+1; i++)
#define rreps(i,x) for(ll i = (ll)(x); 1 <= i; i--)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> Pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
constexpr ll INF = numeric_limits<ll>::max()/4;
constexpr ll n_max = 2e5+10;
#define int ll

template <typename A, typename B>
string to_string(pair<A, B> p);
string to_string(const string &s) {return '"' + s + '"';}
string to_string(const char c) {return to_string((string) &c);}
string to_string(bool b) {return (b ? "true" : "false");}
template <size_t N>
string to_string(bitset<N> v){
    string res = "";
    for(size_t i = 0; i < N; i++) res += static_cast<char>('0' + v[i]);
    return res;
}
template <typename A>
string to_string(A v) {
    bool first = true;
    string res = "{";
    for(const auto &x : v) {
        if(!first) res += ", ";
        first = false;
        res += to_string(x);
    }
    res += "}";
    return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p){return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}

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

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

void YES(bool ok){
    cout << (ok ? "Yes" : "No") << endl;
}
void print() {
    cout << endl;
}

template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
    cout << head;
    if (sizeof...(tail) != 0) cout << " ";
    print(forward<Tail>(tail)...);
}

template <class T>
void print(vector<T> &vec) {
    for (auto& a : vec) {
        cout << a;
        if (&a != &vec.back()) cout << " ";
    }
    cout << endl;
}

template <class T>
void print(vector<vector<T>> &df) {
    for (auto& vec : df) {
        print(vec);
    }
}

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll h,w; cin >> h >> w;
    ll k,l; cin >> k >> l;
    vector<vector<ll>> table(h, vl(w));
    const ll max = 1e9;
    rep(i,h)rep(j,w){
        if((i+1) % k == 0 && (j + 1) % l == 0){
            table[i][j] = -max;
        }
        else if(i % k == 0 && j % l == 0){
            table[i][j] = max - 1;
        }
    }
    ll ans = 0;
    rep(i,h)rep(j,w){
        ans += table[i][j];
    }
    // print(table);
    // debug(ans);
    YES(ans > 0);
    if(ans > 0){
        print(table);
    }
}

Measured memory_bytes: 4992
#include<bits/stdc++.h>
#define maxn 50

using namespace std;
typedef long long ll;
char s[maxn],f[maxn],g[maxn];
int n,m,p,q;
ll dp[20][20],ans;

int main(){
    cin >> n;
    scanf("%s",s);
    for (int i=0;i<(1<<n);i++){
        p=0; q=0;
        for (int j=0;j<n;j++) if (i&(1<<j)) f[p++]=s[j]; else g[q++]=s[j];
        memset(dp,0,sizeof(dp)); dp[0][0]=1;
        for (int j=0;j<n;j++) for (int k=0;k<=j;k++) if (dp[k][j-k]){
            dp[k+1][j-k]+=dp[k][j-k]*(k<p&&s[n*2-j-1]==f[k]);
            dp[k][j-k+1]+=dp[k][j-k]*(j-k<q&&s[n*2-j-1]==g[j-k]);
        }
        ans+=dp[p][q];
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
int main()
{
	int N;
	cin >> N;
	vector<int> p(N);
	
	for (int i = 0; i < N; i++) {
		cin >> p[i];
	}
	int tmp = 0;
	for (int i = 0; i < N; i++) {
		if (p[i] == (i + 1)) { tmp = tmp + 1; }
	}
	if (tmp < (N - 2)) { cout << "NO"; }
	else { cout << "YES"; }
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void){
	int t,n,i,j;
	int prev,current;
	int upmax,downmax;
	scanf("%d",&t);
	for(i = 0; i < t; i++){
		scanf("%d",&n);
		current = -1;
		upmax = 0;
		downmax = 0;
		for(j = 0; j < n; j++){
			prev = current;
			scanf("%d",&current);
			if(prev != -1){
				if(prev > current){
					if(downmax < prev - current){
						downmax = prev - current;
					}
				}else{
					if(upmax < current - prev){
						upmax = current - prev;
					}
				}
			} 
		}
		printf("%d %d\n",upmax,downmax);
	}
	return 0;
}

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

bool issq(int N) {
	for (int i = 0; i <= 10000; i++) {
		if (i * i == N) return true;
	}
	return false;
}

int main()
{
	string a, b;
	cin >> a >> b;
	cout << (issq(stoi(a + b)) ? "Yes" : "No") << endl;
	return 0;
}


Measured memory_bytes: 256
/**
 *      purpose : 
 *      author  : kyomukyomupurin
 *      created : 
**/

// input/output
#include <iostream>
#include <fstream>
#include <sstream>
// container class
#include <array>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
// math, algorithm
#include <algorithm>
#include <cmath>
#include <complex>
#include <numeric>
// etc
#include <bitset>
#include <cassert>
#include <cctype>
#include <cstring>
#include <chrono>
#include <iomanip>
#include <random>
#include <utility>
// using-directive
using namespace std;
// alias template
using int64 = int64_t;
using vi = vector<int>;
using vl = vector<int64_t>;
using pii = pair<int, int>;
using pll = pair<int64_t, int64_t>;
// text macro replacement
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define print(x) cout << (x) << '\n'
#define debug(x) cerr << #x << ": " << (x) << '\n'
// variadic template
template<typename T> inline void chmin(T &a, T b) {if (a > b) a = b; return;}
template<typename T> inline void chmax(T &a, T b) {if (a < b) a = b; return;}


const int64_t INF = 1e18;

struct edge {
  int64_t to, cost;
};

std::vector<edge> G[303030];
int64_t dis[303030];

void dijkstra(int s){
  std::priority_queue<std::pair<int64_t, int64_t>,
                      std::vector<std::pair<int64_t, int64_t>>,
                      std::greater<std::pair<int64_t, int64_t>>> pq;
  std::fill(dis, dis + 303030, INF);
  dis[s] = 0;
  pq.push(std::pair<int64_t, int64_t>(0, s));

  while (!pq.empty()){
    std::pair<int64_t, int64_t> p = pq.top(); pq.pop();
    int v = p.second;
    if (dis[v] < p.first) continue;
    for (int i = 0; i < (int) G[v].size(); ++i){
      edge e = G[v][i];
      if (dis[e.to] > dis[v] + e.cost){
        dis[e.to] = dis[v] + e.cost;
        pq.push(std::pair<int64_t, int64_t>(dis[e.to], e.to));
      }
    }
  }
}

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

  int n, m; cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    int u, v; cin >> u >> v;
    --u; --v;
    G[u * 3].push_back({v * 3 + 1, 1LL});
    G[u * 3 + 1].push_back({v * 3 + 2, 1LL});
    G[u * 3 + 2].push_back({v * 3, 1LL});
  }

  int s, t; cin >> s >> t;
  --s; --t;
  dijkstra(s * 3);
  if (dis[t * 3] == INF) {
    print(-1);
  } else {
    dis[t * 3] /= 3;
    print(dis[t * 3]);
  }

  return 0;
}

Measured memory_bytes: 19072
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define MOD @
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

int N, A[101010], B[101010];
pair<int, int> P[101010];
vector<int> Bs;

int fi(int v)
{
	int p = lower_bound(Bs.begin(), Bs.end(), v) - Bs.begin();
	return p;
}

int ch[101010];

int main()
{
	scanf("%d", &N);
	for (int i = 0; i < N; ++i) scanf("%d", A + i);
	for (int i = 0; i < N; ++i) scanf("%d", B + i);
	for (int i = 0; i < N; ++i) P[i] = make_pair(B[i], A[i]);
	sort(P, P + N);

	sort(A, A + N);
	for (int i = 0; i < N; ++i) {
		if (P[i].first < A[i]) {
			puts("No");
			return 0;
		}
	}

	for (int i = 0; i < N; ++i) Bs.push_back(B[i]);
	sort(Bs.begin(), Bs.end());
	Bs.erase(unique(Bs.begin(), Bs.end()), Bs.end());

	for (int i = 0; i < N; ++i) {
		P[i].first = fi(P[i].first);
		P[i].second = fi(P[i].second);
		//printf("%d %d\n", P[i].first, P[i].second);
	}

	for (int i = 0; i < N; ++i) {
		if (P[i].first != i) {
			puts("Yes");
			return 0;
		}
		if (fi(A[i]) != i) {
			puts("Yes");
			return 0;
		}
	}
	for (int i = 0; i < N; ++i) {
		ch[i] = P[i].second;
	}
	int x = 0, len = 0;
	do {
		++len;
		x = ch[x];
	} while (x != 0);

	if (len == N) puts("No");
	else puts("Yes");
	return 0;
}


Measured memory_bytes: 3184
#include <iostream>
#include <string>

using namespace std;

int main(){
  string in;
  getline(cin, in);
  for(int i=0; i<in.size(); i++){
    char t = in[i];
    if('a' <= t && t <= 'z')
      cout << (char)(t+('A'-'a'));
    else cout << t;
  }
  cout << endl;
  return 0;
}

Measured memory_bytes: 1168
N = int(input())
A_lst = [int(x) for x in input().split()]
B_lst = [0]
for i in range(1, N + 1):
    B_lst.append(A_lst[i - 1] + B_lst[i - 1])
B_lst.sort()
n = 1
ans = 0
for i in range(N + 1):
    if i == N:
        ans += n * (n - 1) // 2
        break
    if B_lst[i] == B_lst[i + 1]:
        n += 1
    else:
        ans += n * (n - 1) // 2
        n = 1
print(ans)


Measured memory_bytes: 25724
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()

    y = [0] * (10**6 + 1)
    z = [0] * (10**6 + 1)
    A = []
    for x in sys.stdin.readline().split():
        x = int(x)
        A.append(x)
        y[x] += 1
        if y[x] == 1:
            c = x * 2
            while c <= 10**6:
                z[c] = 1
                c += x

    ans = 0
    for i in range(N):
        x = A[i]
        if y[x] > 1: continue

        if z[x] == 0:
            ans += 1

    print(ans)
if __name__ == '__main__':
    main()


Measured memory_bytes: 109608
#include<bits/stdc++.h>
#define ll signed long long int
using namespace std;
#define rep(i, c) for(int i = 0; i < (int)c; i++)
const int inf = 1000000000;

 signed main() {
 ll n;
 cin >> n;
 vector<ll> X(n);
 rep(i, n) cin >> X[i];
 ll L = X[0], R = X[0];
 rep(i, n) {
 L = min(L, X[i]);
 R = max(R, X[i]);
 }
 ll ans = inf;
 for(ll i = L; i <= R; i++) {
ll cost = 0;
rep(j, n) cost += (X[j] - i) * (X[j] - i);
ans = min(ans, cost);
 }
 cout << ans << endl;
 return 0;
 }

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long N = scanner.nextLong();
        long A = scanner.nextLong();
        long B = scanner.nextLong();
        long answer = N / (A + B) * A;
        answer += Math.min(N % (A + B), A);
        System.out.println(answer);
    }
}

Measured memory_bytes: 23764
#include<bits/stdc++.h>
using namespace std;
 
#define ll          long long int
#define ld          long double
#define pb          push_back
#define mp          make_pair
#define ff          first
#define se          second
#define endl        '\n'
#define fd(n)       fixed<<setprecision(n)
#define MAX         100000000000000000
#define MAXN        10000005
#define mod         998244353  
#define pi          3.1415926535897932384626433
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s,t;
    cin>>s>>t;
    ll i,count=0;
    for(i=0;i<s.size();i++){
        if(s[i]!=t[i]){
            count++;
        }
    }
    cout<<count;
}

Measured memory_bytes: 3784
#include <iostream>
#include <string>
#include <map>
#include <algorithm>

int main() {
	int n;
	std::cin >> n;

	std::map<std::string, int> map;

	std::string s;
	for (int i = 0; i < n; ++i) {
		std::cin >> s;

		++map[s];
	}

	int max = 0;
	for (auto&& p : map)
		max = std::max(max, p.second);

	for (auto&& p : map)
		if (p.second == max)
			std::cout << p.first << std::endl;
}

Measured memory_bytes: 25216
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define INF (1LL<<50)
#define MOD 1000000007

int main(){
    int N;
    cin >> N;
    int a = N%10;
    string ans;
    if(a==3){
        ans = "bon";
    }else if(a==0||a==1||a==6||a==8){
        ans = "pon";
    }else{
        ans = "hon";
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = int(a); i < int(b); ++i)
typedef long long ll;
long long MOD = 1e9 + 7;
const long long INF = 1LL << 60;
using namespace std;

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 a, b, k;
  cin >> a >> b >> k;
  ll ans_a = a, ans_b = b;

  if (a <= k) {
    ans_a = 0;
    if (b <= k - a) {
      ans_b = 0;
    } else {
      ans_b = b - k + a;
    }
  } else {
    ans_a = a - k;
  }

  cout << ans_a << " " << ans_b << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long long n,a[52],m;
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	  cin>>a[i];
	sort(a+1,a+n+1);
	for(int i=n;i>=n-m+1;i--)
	  a[n+1]+=a[i];
	cout<<a[n+1]<<endl;
	return 0;
}

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

using namespace std;

#define llint long long int
#define REP(i,s,l) for(llint i=s;i<l;i++)
#define DEBUG 0
#define INF (1LL<<50)
#define MOD 1000000007

int main() {

    int time[5];
    cin >> time[0] >> time[1] >> time[2] >> time[3] >> time[4] ;
    int keika = 0;
    int machimax=0;

    REP (i, 0, 5){
     if (machimax <=  (10 - time[i]%10) % 10)  machimax = (10 - time[i]%10) % 10;
    }
    
                    keika += time[0];
                    keika += (10 - time[0]%10) % 10;
                    keika += time[1];
                    keika += (10 - time[1]%10) % 10;
                    keika += time[2];
                    keika += (10 - time[2]%10) % 10;
                    keika += time[3];
                    keika += (10 - time[3]%10) % 10;
                    keika += time[4];
                    keika += (10 - time[4]%10) % 10;
                    keika -= machimax;

                    cout <<  keika << endl;

   return 0;
}

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

using namespace std;

int main() {
    int sx, sy, tx, ty;
    int dx, dy;

    cin >> sx >> sy >> tx >> ty;
    dx = tx - sx;
    dy = ty - sy;

    cout << string(dx, 'R') << string(dy, 'U')
         << string(dx, 'L') << string(dy, 'D')
         << 'D' << string(dx+1, 'R') << string(dy+1, 'U') << 'L'
         << 'U' << string(dx+1, 'L') << string(dy+1, 'D') << 'R' << endl;

    return 0;
}



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

using namespace std;

const int N = 300;
bool occ[N][N];
int a[N][N], x[N][N];

struct graph {
  bool mark[N];
  int mat[N][N];
  int match[N];
  int n;

  graph(int x = 0) {
    n = x;
    memset(mat, 0, sizeof mat);
  }

  void add_edge(int u, int v) {
    ++mat[u][v];
    ++mat[v][u];
  }

  void remove_edge(int u, int v) {
    --mat[u][v];
    --mat[v][u];
  }

  bool dfs(int u) {
    mark[u] = true;
    for (int i = 0; i < n; i++) {
      if (!mat[u][i]) {
        continue;
      }
      if (match[i] == -1 || (!mark[match[i]] && dfs(match[i]))) {
        match[u] = i;
        match[i] = u;
        return true;
      }
    }
    return false;
  }

  vector<int> matching(int upper_size) {
    memset(match, -1, sizeof match);
    while (true) {
      memset(mark, false, sizeof mark);
      bool found = false;
      for (int i = 0; i < upper_size; i++) {
        if (match[i] == -1) {
          found |= dfs(i);
        }
      }
      if (!found) {
        break;
      }
    }
    vector<int> res;
    for (int i = 0; i < upper_size; i++) {
      assert(~match[i]);
      res.push_back(match[i] - upper_size);
    }
    return res;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  graph G(205);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> a[i][j];
      G.add_edge(i, (a[i][j] - 1) / m + n);
    }
  }
  for (int j = 0; j < m; j++) {
    vector<int> cur = G.matching(n);
    for (int i = 0; i < n; i++) {
      for (int c = 0; c < m; c++) {
        if ((a[i][c] - 1) / m == cur[i] && !occ[i][c]) {
          occ[i][c] = true;
          x[i][j] = a[i][c];
          break;
        }
      }
      G.remove_edge(i, cur[i] + n);
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cout << x[i][j] << " \n"[j == m - 1];
    }
  }
  for (int j = 0; j < m; j++) {
    vector<int> cur;
    for (int i = 0; i < n; i++) {
      cur.push_back(x[i][j]);
    }
    sort(cur.begin(), cur.end(), [&](int x, int y) { return (x - 1) / m < (y - 1) / m; });
    for (int i = 0; i < n; i++) {
      x[i][j] = cur[i];
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cout << x[i][j] << " \n"[j == m - 1];
    }
  }
  return 0;
}



Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {
 public static void main(String[] args) {
	Scanner in = new Scanner(System.in);
	int nextsize = in.nextInt();
	int size;
	while (nextsize != 0) {
	 size = nextsize;
	 int max = -100001;
	 int nums = -100001;
	 for (int num = 0; num < size; num++) {
		int a = in.nextInt();
		nums = Math.max(nums + a, a);
		max = Math.max(max, nums);
	 }
	 System.out.println(max);
	 nextsize = in.nextInt();
	}
 }

}

Measured memory_bytes: 12000
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N,sum=0;
  cin >> N;
  for(int i=0;i<N;i++){
    int l,r;
    cin >> l>> r;
    sum += r+1;
    sum -= l;
}
  cout << sum << endl;
}

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

using namespace std;
#define inputInt(a) int a; cin >> a; 
#define inputInt2(a,b) int a; int b; cin >> a >> b; 
#define inputInt3(a,b,c) int a; int b; int c; cin >> a >> b >> c;
#define inputLong(a) long a;cin >> a; 
#define inputIntArray(a,N) int a[N];for(int i=0;i<N;i++){cin >> a[i];}
#define inputLongArray(a,N) long a[N];for(int i=0;i<N;i++){cin >> a[i];}
#define inputIntArray2(a,b,N) int a[N]; int b[N]; for(int i=0;i<N;i++){cin >> a[i] >> b[i];}
#define output(answer) cout << answer << endl;
#define fN(i,N)    for(int i=0; i<N; i++)
#define fSE(i,s,e) for(int i=s; i<=e; i++)
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define FOR(i,N) for(int i=0; i<N; i++)
#define cinv(v,N) vector<int> v(N); for(int i=0; i<N; i++){ cin >> v[i]; }
#define mt make_tuple
const ll MOD2 = 998244353;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

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

  //main
  int N; cin >> N;
  bool flag = 0;
  int ans = 0;
  int q1 = ceil(N/1.08);
  int q2 = floor((N+1)/1.08);
  for(int i=q1; i<=q2; i++){
    if(N == floor(i*1.08)){ flag = 1; ans = i;}
  }
  
  // output
  if(flag){cout << ans << endl;}
  else{ cout << ":(" << endl; }

  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define ALL(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9;
const int MOD = 1000000007;
const double PI = acos(-1);
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

void solve() {
  int n;
  cin >> n;
  if (n < 100) {
    cout << 0 << endl;
    return;
  }
  int h = n/100;
  int d = n%100;
  if (h*5<d) cout << 0 << endl;
  else cout << 1 << endl;
}

int main() {
  solve();
  return 0;
}

Measured memory_bytes: 3620
import java.util.Scanner;
public class Main {
    static final long MOD = 998_244_353;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int S = sc.nextInt();
        int[] A = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = sc.nextInt();
        }
        long ans = 0;
        long[] dp = new long[S + 1]; // dp[S]:= f(L,R) when A_i is used or not.
        for (int i = 0; i < N; i++) {
            // Case when A[i] is not used. This is a seed scaffold.
            dp[0] += 1;

            for (int j = S; j >= A[i]; j--) {
                dp[j] += dp[j - A[i]];
                dp[j] %= MOD;
            }
            ans += dp[S];
            ans %= MOD;
        }
        System.out.println(ans);
    }
}

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

#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ppb pop_back
#define ll long long
#define ull unsigned long long
#define cntbit(x) __builtin_popcount(x)
#define uset unordered_set
#define endl '\n'
#define umap unordered_map
#define pii pair<int, int> 
#define ld long double
#define pll pair<long long, long long> 

const int N = 2e5 + 15;
ll n, x, a[N], ans;
vector <ll> tmp, is;

int main() {
	cin >> n >> x;
	for(ll i = 1; i <= n; ++i) {
		int r; cin >> r;
		is.pb(r);
	}
	is.pb(x);
	sort(is.begin(), is.end());
	for(ll i = 1; i < is.size(); ++i)
		ans = __gcd(ans, is[i] - is[i-1]);
	cout << ans;
	return 0;
}

Measured memory_bytes: 1400
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mp make_pair
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)

int main(){
  string s;
  cin >> s;
  rep(i,s.size()){
    if(i%2==0) cout << s[i];
  }
  return 0;

}


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

int main() {
	long n,c=1,r=0;
	cin>>n;
	vector<long>v(n);
	for(int i=0;i<n;i++)cin>>v.at(i);
	sort(v.begin(),v.end());
	for(int i=0;i<n-1;i++){
		if(v.at(i)!=v.at(i+1)){
			c++;
			r=(i+1);
		}
	}
	if(n>=3){
		
	
	if(c==1){
		if(v.at(0)==(n-1)||v.at(0)<=n/2){
			cout<<"Yes"<<endl;
		}
		else{
			cout<<"No"<<endl;
		}
	}
	else if(c==2){
		if((2*v.at(0)+2)<=(r+n)&&r<=v.at(0)&&v.at(1)!=1){
			
			if(v.at(0)!=1){
			cout<<"Yes"<<endl;
			
			}
			else{
				if(v.at(1)==2){
					cout<<"Yes"<<endl;
				}  
				
				else{
					cout<<"No"<<endl;
				}
			}
		
		}
		else{
			cout<<"No"<<endl;
		}
	
	}
	else{
		cout<<"No"<<endl;
		
	}
	}
	else{
		if(v.at(0)==v.at(1)&&v.at(1)==1){
			cout<<"Yes"<<endl;
		}
		else{
			cout<<"No"<<endl;
		}
	}
	return 0;
}

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

using namespace std;
#define ll long long
#define ld long double

int main()
{
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
    int n;
    ll h;
    cin >> n >> h;
    vector<ll> a(n), b(n);
    for(int i=0;i<n;i++) cin >> a[i] >> b[i];
    sort(a.begin(), a.end(), greater<int>());
    sort(b.begin(), b.end(), greater<int>());
    int ans = 0;
    ll sum = 0;
    bool ok = false;
    for(int i=0;i<n;i++) {
        if(b[i] > a[0]) {
            sum += b[i];
            ans++;
        }
        if(sum >= h) {
            ok = true;
            break;
        }
    }
    if(!ok) {
        ans += ceil((h - sum) / (ld)a[0]);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define FOR(i,L,R) for(i=L;i<R;i++)
#define REP(i,N) FOR(i,0,N)
int main(){
  ll N,A,B,C,ans=1000000000,s=1,i;cin>>N>>A>>B>>C;ll L[N];
  REP(i,N){s*=4;cin>>L[i];}
  REP(i,s){
    ll p=i,j,d[4]={0,0,0,0},c[4]={0,0,0,0};
    REP(j,N){d[p%4]+=L[j];c[p%4]++;p/=4;}
    if(c[0]&&c[1]&&c[2])ans=min(ans,abs(d[0]-A)+abs(d[1]-B)+abs(d[2]-C)+10*(c[0]+c[1]+c[2])-30);
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 3576
using System;
using System.Collections.Generic;
using System.Collections;
using System.Collections.Specialized;
using System.Linq;
using System.Text;
using System.IO;
using System.Reflection;
using static System.Math;
using System.Numerics;
static class Program{
	const int mod=(int)1e9+7;
	static void Main(){
		Sc sc=new Sc();
		var n=sc.I;
		var a=sc.Arr(n,()=>sc.Ia);
		var h=new long[n][];
		Array.Sort(a,(u,v)=>u[0]-v[0]);
		a=a.OrderBy(x=>x[0]).ThenByDescending(x=>x[1]).ToArray();
		for(int i = n-1;i>=0;i--) {
			h[i]=new long[]{0,a[i][0],0,a[i][1]};
			if(i!=n-1){
				h[i][1]=Max(h[i+1][1],h[i][1]);
				h[i][3]=Min(h[i+1][3],h[i][3]);
			}
		}
		long ans=0;
		for(int i = 0;i<n;i++) {
			h[i][0]=a[i][1];
			if(i!=0){h[i][0]=Min(h[i-1][0],h[i][0]);}
			if(i!=n-1){
				long p=Max(0,1+h[i][0]-a[i][0]);
				long q=Max(0,1+h[i+1][3]-h[i+1][1]);
				ans=Max(ans,p+q);
				if(i!=0){
					p=Max(0,1+a[i][1]-a[i][0]);
					q=Max(0,1+h[0][3]-a[n-1][0]);
					ans=Max(ans,p+q);
				}
			}
		}
		Console.WriteLine("{0}",ans);
	}
}

public class Sc{
	public int I{get{return int.Parse(Console.ReadLine());}}
	public long L{get{return long.Parse(Console.ReadLine());}}
	public double D{get{return double.Parse(Console.ReadLine());}}
	public string S{get{return Console.ReadLine();}}
	public int[] Ia{get{return Array.ConvertAll(Console.ReadLine().Split(),int.Parse);}}
	public long[] La{get{return Array.ConvertAll(Console.ReadLine().Split(),long.Parse);}}
	public double[] Da{get{return Array.ConvertAll(Console.ReadLine().Split(),double.Parse);}}
	public string[] Sa{get{return Console.ReadLine().Split();}}
	public object[] Oa{get{return Console.ReadLine().Split();}}
	public int[] Ia2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),int.Parse);}}
	public int[] Ia3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),int.Parse);}
	public int[] Ia3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),int.Parse);}
	public long[] La2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),long.Parse);}}
	public long[] La3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),long.Parse);}
	public long[] La3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),long.Parse);}
	public T[] Arr<T>(int n,Func<T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f();}return a;}
	public T[] Arr<T>(int n,Func<int,T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(i);}return a;}
	public T[] Arr<T>(int n,Func<string[],T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(Console.ReadLine().Split());}return a;}
	public T[] Arr<T>(int n,Func<int,string[],T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(i,Console.ReadLine().Split());}return a;}
}

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

int main() {
  int a , b = 0;
  cin >> a;
  for(int i = 0; i < 3; i++) {
    if ( a %10 == 1){
      b=b+1;
    };
    a=a/10;
  }
  cout << b << endl;
}


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


int main() {

	int r, g, b, n;
	cin >> r >> g >> b >> n;
	int cnt = 0;

	for (int i = 0; i <= n/r; i++) {//500
		for (int j = 0; j <= n/g; j++) {//100
			
			int sum = r * i + g * j;//R,Gの個数
			if (sum <= n) {

				int others = n - sum;
							   
				if (others % b == 0) {
					cnt++;
				}
			}
		}
	}

	cout << cnt << endl;

	return 0;
}


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

int main() {
  ll a,b,c;
  cin>>a>>b>>c;
  ll d=c-a-b;
  if(d>0 && d*d>4*a*b) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}


Measured memory_bytes: 256
def c171(n):

    ans = ""
    while n > 0:
        n -= 1
        ans += chr(ord('a') + n % 26)
        n //= 26

    return ans[::-1]

def main():
    n = int(input())
    print(c171(n))

if __name__ == '__main__':
    main()


Measured memory_bytes: 61296
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br =
				new BufferedReader(new InputStreamReader(System.in));

		while (true) {
			int n = Integer.parseInt(br.readLine());
			if (n == 0) break;
			int sum = 0, div = 5;
			while (n / div != 0) {
				sum += n / div;
				div *= 5;
			}
			System.out.println(sum);
		}

	}

}

Measured memory_bytes: 16868
import java.util.*;

public class Main {
  public static void main(String[] args) {
    long MOD = (long)Math.pow(10, 9) + 7;
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] a = new int[n];
    for(int i = 0; i < n; i++) {
      a[i] = sc.nextInt();
    }
    int[] b = new int[n + 1];
    b[0] = 0;
    for(int i = 0; i < n; i++) {
      b[i + 1] = b[i] ^ a[i];
    }
    long ans = 0;
    if(b[n] != 0) {
      int p = b[n];
      long[] dp1 = new long[n + 1];
      long[] dp2 = new long[n + 1];
      dp1[0] = 1;
      dp2[0] = 0;
      for(int i = 1; i < n + 1; i++) {
        if(b[i] == 0) {
          dp1[i] = (dp1[i - 1] + dp2[i - 1]) % MOD;
        } else {
          dp1[i] = dp1[i - 1];
        }
        if(b[i] == p) {
          dp2[i] = (dp2[i - 1] + dp1[i - 1]) % MOD;
        } else {
          dp2[i] = dp2[i - 1];
        }
      }
      ans = (dp2[n] - dp2[n - 1] + MOD) % MOD;
    } else {
      long kosuu = 0;
      long[] q = new long[n + 1];
      q[0] = 1;
      for(int i = 1; i < n + 1; i++) {
        if(b[i] == 0) {
          q[i] = q[i - 1] + 1;
        } else {
          q[i] = q[i - 1];
        }
      }
      kosuu = q[n - 1] - q[0];
      long t = 1;
      for(long i = 0; i < kosuu; i++) {
        t = (t * 2) % MOD;
      }
      ans = t;
      HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();
      for(int i = 1; i < n; i++) {
        if(b[i] != 0) {
          if(map.containsKey(b[i])) {
            ArrayList<Integer> list = map.get(b[i]);
            list.add(i);
            map.put(b[i], list);
          } else {
            ArrayList<Integer> list = new ArrayList<Integer>();
            list.add(i);
            map.put(b[i], list);
          }
        }
      }
      for(int p : map.keySet()) {
        ArrayList<Integer> list = map.get(p);
        int x = list.size();
        long[] dp1 = new long[x];
        long[] dp2 = new long[x];
        dp1[0] = 1;
        dp2[0] = 1;
        for(int i = 1; i < x; i++) {
          int k = list.get(i);
          int s = list.get(i - 1);
          long w = q[k] - q[s];
          long m = (dp1[i - 1] * w) % MOD;
          dp1[i] = (dp1[i - 1] + m + dp2[i - 1]) % MOD;
          dp2[i] = (m + dp2[i - 1]) % MOD;
        }
        ans = (ans + dp1[x - 1]) % MOD;
      }
    }
    System.out.println(ans);
  }
}

Measured memory_bytes: 201664
import math
import bisect
import collections
import itertools
import heapq
import string
import sys
sys.setrecursionlimit(10**9)
def gcd(a,b):return math.gcd #最大公約数
def lcm(a,b):return (a*b) // math.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i: divisors.append(n//i)
    return divisors
def is_prime(n):
    if n == 1: return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0: return False 
    return True
def primes(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n + 1, i): is_prime[j] = False
    return [i for i in range(n+1) if is_prime[i]]
def sieve_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

N = iin()
a = iln()
if sum(a) == 0:
    print('Yes')
    exit()

if N % 3 != 0:
    print('No')
else:
    d = {}
    for i in range(N):
        if a[i] not in d.keys():
            d[a[i]] = 1
        else:
            d[a[i]] += 1
    if len(d) == 3:
        keys = list(d.keys())
        values = list(d.values())
        if values[0] == values[1] == values[2] and keys[0] ^ keys[1] == keys[2]:
            print('Yes')
        else:
            print('No')
    elif len(d) == 2:
        if 0 in d.keys() and d[0] == N//3:
            print('Yes')
        else:
            print('No')
    else:
        print('No')


Measured memory_bytes: 15444
import java.util.*;

public class Main {
	Scanner in = new Scanner(System.in);
	public static void main(String[] args) {
		new Main();
	}

	public Main() {
		while(true){
			int w = in.nextInt();
			int h = in.nextInt();
			if(w+h==0)break;
			new AOJ1150().doIt(w, h);
		}
	}
	class AOJ1150{
		void doIt(int w,int h){
			char[][] map = new char[h][w];
			for(int i=0;i<h;i++)for(int s=0;s<w;s++)map[i][s] = in.next().charAt(0);
//
//			for(int i=0;i<h;i++){
//				for(int s=0;s<w;s++)System.out.print(map[i][s]+" ");
//				System.out.println();
//			}

			PriorityQueue<State> q = new PriorityQueue<State>();
			for(int i=0;i<h;i++)for(int s=0;s<w;s++)if(map[i][s]=='S'){
				q.add(new State(s, i, 0, 0));
				q.add(new State(s, i, 0, 1));
			}

			int[][][] maps = new int[h][w][2];
			for(int i=0;i<h;i++)for(int s=0;s<w;s++){
				maps[i][s][0] = Integer.MAX_VALUE/2;
				maps[i][s][1] = Integer.MAX_VALUE/2;
			}
			int result = -1;
			while(q.size()>0){
				State now = q.remove();
				int x = now.x,y = now.y;
				if(map[y][x]=='T'){
					result = now.step;break;
				}else if(map[y][x]=='X'){
					continue;
				}else if(map[y][x]=='S'){
					now.step += 0;
				}else{
					now.step += Integer.parseInt(""+map[y][x]);
				}
				if(maps[y][x][now.foot]<=now.step)continue;
				maps[y][x][now.foot] = now.step;
				if(now.foot==0){//次に動かすのは右
					for(int px=1;px<=3;px++)for(int py=-2;py<=2;py++){
						int nx = px+x, ny = py+y;
						if(nx<0||nx>=w||ny<0||ny>=h)continue;
						if(Math.abs(nx-x)+Math.abs(ny-y)>3)continue;	
						q.add(new State(nx, ny, now.step, 1));
					}
				}else if(now.foot==1){//次に動かすのは左
					for(int px=-3;px<0;px++)for(int py=-2;py<=2;py++){
						int nx = px+x, ny = py+y;
						if(nx<0||nx>=w||ny<0||ny>=h)continue;
						if(Math.abs(nx-x)+Math.abs(ny-y)>3)continue;						
						q.add(new State(nx, ny, now.step, 0));
					}
				}
			}
			
//			System.out.println("right");
//			for(int i=0;i<h;i++){
//				for(int s=0;s<w;s++)System.out.printf("%10d ",maps[i][s][0]);
//				System.out.println();
//			}
//			System.out.println("\n left");
//			for(int i=0;i<h;i++){
//				for(int s=0;s<w;s++)System.out.printf("%10d ",maps[i][s][1]);
//				System.out.println();
//			}
			
//			for(int i=0;i<h;i++)for(int s=0;s<w;s++)if(map[i][s]=='T'){
//				result = Math.min(result, Math.min(maps[i][s][0], maps[i][s][1]));
//			}
			System.out.println(result);
		}
		class State implements Comparable<State>{
			int x,y,step,foot;//1なら右、0で左
			public State(int x,int y,int step,int foot) {
				this.x = x;this.y = y;this.step = step;this.foot = foot;
			}
			public int compareTo(State o) {
				return this.step - o.step;
			}
		}
	}
}

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

const int MOD = 1000000007;
const int INF_32 = 1LL << 30;
const int64_t INF_64 = 1LL << 60;

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;
}

typedef long long ll;

#define MAX_N 10000

struct Edge {
    int to;
    int weight;
    Edge(int t, int w)
        : to(t)
        , weight(w)
    {
    }
};
using Graph = vector<vector<int>>;
using Graph_e = vector<vector<Edge>>;

vector<int> dx = { 1, 0, -1, 0 };
vector<int> dy = { 0, 1, 0, -1 };
typedef pair<int, int> P;

int main()
{
    int N;
    cin >> N;
    vector<ll> a(N * 3);
    rep(i, 3 * N) cin >> a.at(i);

    //左から前処理
    vector<ll> S(N * 2 + 1, 0); // S.at(i)はa.at(i-1)までのN個の要素で最大和
    priority_queue<ll, vector<ll>, greater<ll>> que1;

    rep(i, N)
    {
        S.at(i + 1) = S.at(i) + a.at(i);
        que1.push(a.at(i));
    }
    for (int i = N; i < 2 * N; i++) {
        que1.push(a.at(i));
        ll mi = que1.top();
        que1.pop();
        S.at(i + 1) = S.at(i) + a.at(i) - mi;
    }

    //右から前処理
    vector<ll> T(N * 2 + 1, 0);
    priority_queue<ll> que2;

    rep(i, N)
    {
        T.at(i + 1) = T.at(i) + a.at(3 * N - 1 - i);
        que2.push(a.at(3 * N - 1 - i));
    }
    for (int i = N; i < 2 * N; i++) {
        que2.push(a.at(3 * N - 1 - i));
        ll ma = que2.top();
        que2.pop();
        T.at(i + 1) = T.at(i) + a.at(3 * N - 1 - i) - ma;
    }

    // 集計
    ll res = -(1LL << 60);
    for (int i = N; i <= 2 * N; i++) {
        res = max(res, S.at(i) - T.at(3 * N - i));
    }
    cout << res << endl;
}


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

int main(){
  string n;
  cin >> n;
  
  int sum=0;
  
  for(int i=0;i<n.length();i++){
    sum+=n[i]-'0';  
  }
  
  if(sum%9==0) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;

 return 0;
}


Measured memory_bytes: 3744