akhauriyash/Code-Regression huggingface dataset:
fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());
    let n: usize = sc.read();
    let x: Vec<i64> = sc.vec(n);
    let l: i64 = sc.read();

    let doubling = calc_doubling(&x, l);
    let last = x[n - 1];
    let inv_x = x.into_iter().map(|x| last - x).rev().collect::<Vec<_>>();
    let inv_doubling = calc_doubling(&inv_x, l);

    let q: usize = sc.read();
    for _ in 0..q {
        let a: usize = sc.read();
        let b: usize = sc.read();

        let (a, b, doubling) = if a < b {
            (a - 1, b - 1, &doubling)
        } else {
            (n - a, n - b, &inv_doubling)
        };

        let mut cur = a;
        let mut ans = 0;
        for d in (0..doubling.len()).rev() {
            let next = doubling[d][cur];
            if next < b {
                cur = next;
                ans += 1 << d;
            }
        }
        sc.write(ans + 1);
        sc.write("\n");
    }
}

fn calc_doubling(x: &Vec<i64>, l: i64) -> Vec<Vec<usize>> {
    let n = x.len();
    let mut doubling = vec![vec![0; n]; 40];
    let mut tail = 0;
    for from in 0..n {
        while tail + 1 < n && x[tail + 1] - x[from] <= l {
            tail += 1;
        }
        doubling[0][from] = tail;
    }

    for d in 0..(doubling.len() - 1) {
        for i in 0..n {
            let next = doubling[d][i];
            let next = doubling[d][next];
            doubling[d + 1][i] = next;
        }
    }
    doubling
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> Self {
        IO(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write(s.to_string().as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


Measured memory_bytes: 88828
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define all(x) x.begin(),x.end()
#define pll  pair <long long,long long>
#define ss second
#define ff first
#define inf 9223372036854775807
#define maa 1000000007
#define ld long double
#define fast  ios_base::sync_with_stdio(false);cin.tie(NULL);
#define bug(x) cout << #x <<": " << x << '\n';
const ll N=1001;
ll n,m ;
ll mask[1001] ;
ll cost[1001] ;
ll dp[1001][(1<<12)] ;
ll fun(ll i,ll  j)
{
  //  cout<<i<<" "<<j<<endl ;
    if(i==m)
    {
        if(j==(1<<n)-1)
            return 0 ;


        return INT_MAX ;
    }
    else if(dp[i][j]!=-1)
        return dp[i][j] ;
    else
    {
        ll ans=fun(i+1,j) ;
        ll nm=j|mask[i] ;
        ans=min(ans,cost[i]+fun(i+1,nm)) ;
        //cout<<i<<" "<<j<<" "<<ans<<endl ;
        return dp[i][j]=ans ;
    }
}
int main()
{
   fast ;
   cin>>n>>m ;
   for(ll i=0;i<m;i++)
   {
       ll x ;
       cin>>cost[i]>>x ;
       ll nm=0 ;
       for(ll j=0;j<x;j++)
       {
           ll y ;
           cin>>y ;
           y-- ;
           nm|=(1<<y) ;
       }
       mask[i]=nm ;
   }
   ll ans=INT_MAX ;
   for(ll i=0;i<1001;i++)
   {
       for(ll j=0;j<(1<<12);j++)
        dp[i][j]=-1 ;
   }
   ans=min(ans,fun(0,0)) ;
   if(ans==INT_MAX)
   cout<<"-1"<<endl ;
   else
   cout<<ans<<endl ;


}


Measured memory_bytes: 32384
#include <stdio.h>
int main(){
 long long int a ,b , c ,x ,y ,gcd ,lcm;
 while( scanf( "%llu %llu" ,&a ,&b ) != EOF ){
   x = a;
   y = b;
   
   while( a % b != 0 ){ /* 最大公約数を求める */
     c = a % b;
     a = b;
     b =c;
   }
   
   gcd = b;
   
   lcm = (x * y) / gcd;
   
   printf( "%llu %llu\n" ,gcd ,lcm );
 }
 return 0;
} 

Measured memory_bytes: 604
#include<bits/stdc++.h>
/************************************************/
#define rep(i,n) for(int i=0;i<n;i++)
#define mp make_pair
#define pb push_back
#define fr first
#define se second
#define forn(i,a,n) for(int i=a;i<n;i++)
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();i++)
#define pii pair<int,int>
#define vi vector<int>
#define ll long long
#define sz(s) s.size()
#define all(s) s.begin(),s.end()
#define zero(x) memset(x,0,sizeof(x))
#define vii vector<pair<int,int> >
#define mpis map<int,string>
#define mpii map<int,int>
#define mpsi map<string,int>
#define re return
/************************************************/
using namespace std;
int a,b; 
int main(){
	cin>>a>>b;
	if(max(a,b)>9||max(a,b)<1)
	cout<<-1;
	else
	cout<<a*b;
	re 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#define M 10000000
#define bag cout<<"here\n"
using namespace std;
int main()
{
    long int v,h,a,b,c;
    while(cin>>v)
    {
        int arr[v];
        for(int i=0;i<v;i++)
          arr[i]=i+1;
        cin>>h;
        for(int i=1;i<=h;i++)
        {
           scanf("%d %*c %d",&a,&b);
           swap(arr[a-1],arr[b-1]);
        }
        for(int i=0;i<v;i++)
          cout<<arr[i]<<endl;
    }
    return 0;
}

Measured memory_bytes: 1244
#include<iostream>
#include<string>
#include<algorithm>    
#include<cmath>
#include<map>
#include<vector>
#include<math.h>
#include<stdio.h>
#include<queue>
using namespace std;
const int MAX_N = 1 << 17;
int n, dat[2 * MAX_N - 1];
void init(int n_) {
	n = 1;
	while (n < n_) { n *= 2; }
	for(int i = 0; i < 2 * n - 1; i++){ dat[i] = 2147483647; }
}
void update(int k, int a) {
	k += n - 1;
	dat[k] = a;
	while (k > 0) {
		k = (k - 1) / 2;
		dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]);
	}
}
int query(int a, int b, int k, int l, int r) {
	if (r <= a || b <= l) return 2147483647;
	if (a <= l && r <= b) return dat[k];
	else {
		int vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
		int vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
		return min(vl, vr);
	}
}
signed main() {
	int m, q, com, x, y; cin >> m >> q;
	init(m);
	for (int h = 0; h < q; h++) { 
		cin >> com >> x >> y;
		if (com == 0) { update(x, y); }
		else {
			cout << query(x, y + 1, 0, 0, n) << endl;
		}
	}
}


Measured memory_bytes: 4120
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;


int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  string s;
  cin >> s;
  int hash[26];
  memset(hash,0,sizeof(hash));
  for(int i=0;i<s.size();i++){
    hash[s[i]-'a']++;
  }
  bool flag=false;
  for(int i=0;i<26;i++){
    //printf("%d is hash[%d]\n",hash[i],i);
    if(hash[i]%2!=0){
      flag=true;
      break;
    }
  }
  if(flag==false)cout <<  "Yes" << endl;
  else cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 256
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        PrintWriter out = new PrintWriter(System.out);
        InputStreamScanner in = new InputStreamScanner(System.in);
        new Main().solve(in, out);
        out.flush();
    }

    private void solve(InputStreamScanner in, PrintWriter out) {
        char[] o = in.next().toCharArray();
        char[] e = in.next().toCharArray();

        for (int i = 1; i <= o.length + e.length; i++) {
            if (i % 2 == 0) {
                out.print(e[i / 2 - 1]);
            } else {
                out.print(o[i / 2]);
            }
        }
    }

    static class InputStreamScanner {

        private InputStream in;

        private byte[] buf = new byte[1024];
        private int len = 0;
        private int off = 0;

        InputStreamScanner(InputStream in)	{
            this.in = in;
        }

        String next() {
            StringBuilder sb = new StringBuilder();
            for (int b = skip(); !isSpace(b);){
                sb.appendCodePoint(b);
                b = read();
            }
            return sb.toString();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        char nextChar() {
            return (char)skip();
        }

        int skip() {
            for (int b; (b = read()) != -1;) {
                if (!isSpace(b)) {
                    return b;
                }
            }
            return -1;
        }

        private boolean isSpace(int c) {
            return c < 33 || c > 126;
        }

        private int read() {
            if (len == -1) {
                throw new InputMismatchException("End of Input");
            }
            if (off >= len){
                off = 0;
                try {
                    len = in.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException(e.getMessage());
                }
                if (len <= 0) {
                    return -1;
                }
            }
            return buf[off++];
        }
    }
}

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

using namespace std;

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

  int k, s;
  cin >> k >> s;

  // x!=y!=z
  int cnt = 0;
  for (int x = 0; x <= k; ++x) {
    for (int y = x + 1; y <= k; ++y) {
      int z = s - x - y;
      if (0 <= z && y < z && z <= k) {
        cnt += 1;
      }
    }
  }
  cnt *= 6;

  // x==y!=z
  int cnt2 = 0;
  for (int x = 0; x <= k; ++x) {
    int z = s - x - x;
    if (0 <= z && z != x && z <= k) {
      cnt2 += 1;
    }
  }
  cnt2 *= 3;

  int cnt3 = 0;
  if (s % 3 == 0 && s / 3 <= k) {
    cnt3++;
  }
  // cout << cnt << cnt2 << cnt3 << "\n";
  cout << (cnt + cnt2 + cnt3) << "\n";
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
#include<complex>
using namespace std;

#define rep(i,x) for(ll i=0;i<x;i++)
#define repn(i,x) for(ll i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 4000001;
const long double eps = 1E-14;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

ll gcd(ll a, ll b) {
	if (b == 0) { return a; }
	if (a < b) { return gcd(b, a); }
	return gcd(b, a % b);
}

ll lcm(ll a, ll b) {
	return a / gcd(a, b) * b;
}

struct edge {
	ll ind;
	ll fr;
	ll to;
	ll d;
};

class mint {
	long long x;
public:
	mint(long long 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*(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;
	}

	friend ostream& operator<<(ostream& os, const mint& m) {
		os << m.x;
		return os;
	}
};

mint pw(mint a, ll b) {
	if (b == 0) { return 1; }
	mint ret = pw(a, b >> 1);
	ret *= ret;
	if (b & 1) { ret *= a; }
	return ret;
}

typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<vector<vector<ll>>> vvvll;

typedef vector<mint> vmint;
typedef vector<vector<mint>> vvmint;
typedef vector<vector<vector<mint>>> vvvmint;

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

int main() {
	ll N, M;
	cin >> N >> M;

	ll L = max(N, M);
	vvvll mat(L + 1);

	mat[0].assign(1, vll(1, 0));

	repn(i, L) {
		ll K = 1 << i;

		mat[i].assign(K, vll(K, 0));

		rep(x, K)rep(y, K) {
			ll t = mat[i - 1][x % (K / 2)][y % (K / 2)];
			if (x >= K / 2 && y >= K / 2) { mat[i][x][y] = 1 - t; }
			else { mat[i][x][y] = t; }
		}

		//rep(x, K) {
			//rep(y, K)cout << mat[i][x][y];
			//cout << endl;
		//}
	}

	vvll ans(1 << L, vll(1 << L, 0));
	repn(x, (1 << L) - 1)repn(y, (1 << L) - 1) {
		ans[x][y] = (mat[L][x - 1][y] + mat[L][x][y - 1] + mat[L][x - 1][y - 1]  +mat[L][x][y]) % 2;
	}

	repn(x, (1 << N) - 1) {
		repn(y, (1 << M) - 1)cout << ans[x][y];
		cout << endl;
	}
}

Measured memory_bytes: 22520
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
template <typename T>
inline bool chmin (T& a, T b)
{
  if(a > b)
  {
    a = b;
    return true;
  }
  return false;
}

int main()
{
  long long N, K;
  cin >> N >> K;
  vector<long long> h (N);
  rep(i, N)
  {
    cin >> h[i];
  }
  vector<long long> dp (N, INFINITY);
  dp[0] = 0;

  for(long long i = 1; i < N; i++)
  {
    for(long long j = 1; j <= K; j++)
    {
      if(i >= j)
      {
        chmin(dp[i], dp[i - j] + abs(h[i] - h[i - j]));
      }
    }
  }

  //for(long long x : dp) cout << x << " ";
  cout << dp[N-1] << endl;
}

Measured memory_bytes: 4816
#include <vector>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long int ll;

#define REP(i, n) for(ll i = 0; i < (ll)(n); i++)

int main(int argc, const char * argv[]) {
    
    ll N, m1 = 0, m2 = 0;
    cin >> N;
    vector<ll> data = vector<ll>(N, 0);
    for (ll i = 0; i < N; i++) {
        ll x;
        cin >> x;
        data[i] = x;
        if (x >= m1) {
            m2 = m1;
            m1 = x;
        } else if (x >= m2) {
            m2 = x;
        }
    }
    
    for (ll i = 0; i < N; i++) {
        if (data[i] == m1) {
            cout << m2 << endl;
        } else {
            cout << m1 << endl;
        }
    }
    
    return 0;
}


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

int main() {
  string a, b;
  cin >> a >> b;
  int num = stoi(a+b);
  bool flag = false;
  for (int i = 1; i <= 1000; i++)
  {
    if ((i*i) == num) {
      cout << "Yes" << endl;
      return 0;
    }
  }
  puts("No");
}




Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iterator>
#include <array>
#include <limits>
#define _USE_MATH_DEFINES
#include <cmath>

using namespace std;

#define REP(i,n) FOR(i,0,n)
#define FOR(i,a,b) for(int i = (a); i < (b); i++)
// For debug
#ifdef _DEBUG
#define DD(x) cerr << #x << ":" << x << endl;
#define DDA(ary) \
cerr << #ary << ":" << endl;\
for (auto v : ary) { cerr << v << ","; }\
cerr << endl;
#else
#define DD(x)
#define DDA(ary)
#endif

const int MAX_N = 100005;

int n;
int main() {
	string line;
	cin >> line;
	n = line.length();
	int gn, pn;
	gn = pn = 1;
	for (char c : line) {
		if (c == 'g') gn++;
		else pn++;
	}
	int ans = floor((gn - pn) / 2);
	cout << ans << endl;

	return 0;
}

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

int main(){
  string x;
  cin>>x;
  int scnt=0,tcnt=0;
  for(int i=0;i<x.size();i++){
    if(x[i]=='S') scnt++;
    else tcnt++;
  }
  int stock=0;
  int remain=0;
  for(int i=0;i<x.size();i++){
    if(x[i]=='S'){
      stock++;
    }
    else{
      if(stock==0){
	remain++;
      }
      else{
	stock--;
      }
    }
  }
  cout<<remain+(scnt-(tcnt-remain))<<endl;
  return 0;

}


Measured memory_bytes: 640
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
    int t,w,s[1005];
    while(~scanf("%d%d",&t,&w))
    {
        int sum=0,maxn=t;
        for(int i=0;i<t;i++)
        {
            scanf("%d",&s[i]);
            sum+=s[i];
        }
        w-=sum;
        for(int i=0;i<t;i++)
        {
            int s1=w/s[i]+t;
            if(s1>maxn)
                maxn=s1;
        }
        printf("%d\n",maxn);
    }
    return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
const long long maxn=1e5+1;
long long dp[maxn],a[maxn];
int main()
{
    long long n,i,j,k;
    cin>>n>>k;
    for (i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    dp[1]=0,dp[2]=abs(a[2]-a[1]);
    for (i=3;i<=n;i++)
    {
        dp[i]=dp[i-1]+abs(a[i]-a[i-1]);
        for (j=2;j<=min(k,i-1);j++) dp[i]=min(dp[i],dp[i-j]+abs(a[i]-a[i-j]));
    }
    cout<<dp[n]<<endl;
}


Measured memory_bytes: 5160
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main(){

   string s;
   vector<int> ans;

   cin >> s;

   while(s != "0"){
      int sum = 0;
      for(int i = 0; i < s.length(); i++){
         sum += s[i] - '0';
      }

      ans.push_back(sum);

      cin >> s;
   }

   for(int i = 0; i < ans.size(); i++){
      cout << ans[i] << endl;
   }

   return 0;
}


Measured memory_bytes: 3164
#include <bits/stdc++.h>
using namespace std;
 
int c, o, y, sisa;
 
int main () {
	cin >> c >> o >> y;
	sisa = o + y - c;
	if (sisa<0){
		cout << "0" << endl;
	} else {
		cout << sisa << endl;
	}
}

Measured memory_bytes: 256
a, v = map(int, input().split())
b, w = map(int, input().split())
t = int(input())
ans = "NO"
if a <= b:
  if v * t + a >= w * t + b:
    ans = "YES"
else:
  if a - (v * t) <= b - (w * t):
    ans = "YES"
print(ans)

Measured memory_bytes: 9184
#include<iostream>
#include<string>
#define REP(i,a,b) for(int i=(int)(a);i<(int)(b);++i)

using namespace std;

int main(){
  string s;
  int K;
  cin>>s;
  cin>>K;
  int size = s.size();
  REP(i,0,size-1){
    if(s[i] == 'a') continue;
    int t = 26-s[i]+'a';
    if(t <= K){
      s[i] = 'a';
      K -= t;
    }    
  }
  s[size-1] = (s[size-1] - 'a' + K)%26 + 'a';
  cout<<s<<endl;
  return 0;
}


Measured memory_bytes: 640
s=input()

matsu=["dream","dreamer","erase","eraser"]

i=len(s)
while 0<i:
    if s[i-5:i] in matsu:
        i-=5
        continue
    elif s[i-6:i] in matsu:
        i-=6
    elif s[i-7:i] in matsu:
        i-=7
    else:
        break
if i==0:
    print("YES")
else:
    print("NO")

Measured memory_bytes: 39792
MOD = 10 ** 9 + 7
n, m = map(int, input().split())
x = list(map(int, input().split()))
y = list(map(int, input().split()))

# 前計算
for i in range(n - 1):
    x[i] = x[i + 1] - x[i]

for i in range(m - 1):
    y[i] = y[i + 1] - y[i]

N = [n - 1]
for i in range(n - 3, 0, -2):
    N.append(N[-1] + i)
    # N.append((N[i] + (n - 1 - 2 * (i + 1))) % MOD)

M = [m - 1]
for i in range(m - 3, 0, -2):
    M.append(M[-1] + i)
    # M.append((M[i] + (m - 1- 2 * (i + 1))) % MOD)

if N[0] % 2 == 0:
    N += N[::-1]
elif N[0] != 1:
    N += N[-2::-1]

if M[0] % 2 == 0:
    M += M[::-1]
elif M[0] != 1:
    M += M[-2::-1]

# print (x)
# print (y)
# print (N)
# print (M)

if len(x) - 1 > len(N):
    while True:
        pass

if len(y) - 1 > len(M):
    while True:
        pass


X_sum = 0
for i in range(n - 1):
    X_sum += x[i] * N[i]
    X_sum %= MOD

Y_sum = 0
for i in range(m - 1):
    Y_sum += y[i] * M[i]
    Y_sum %= MOD

print ((X_sum * Y_sum) % MOD)

Measured memory_bytes: 18556
#include <stdio.h>

int main (){
	int batas, angka1, angka2;
	scanf ("%d %d %d", &batas, &angka1, &angka2);
	int sum =0;
	for (int i=1; i <= batas; i++){
		int hitungDigit = 0;
		int temp = i;
		
		while (temp != 0){
			hitungDigit = hitungDigit + temp%10;
			temp /= 10;
		}
		if (hitungDigit >= angka1 && hitungDigit <= angka2){
			sum += i;
		}
	}
	printf("%d\n", sum);
	
	return 0;
}

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

typedef long long ll;

int n;
int a[2005];
int v[2005];
ll dp[2005][2005];

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    iota(v,v+1+n,0);
    sort(v+1,v+1+n,[](const int &i,const int &j){
        return a[i]>a[j];
    });
    memset(dp,0xC0,sizeof(dp));
    dp[0][0]=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=i;j++){
            if(j>0)dp[i][j]=max(dp[i][j],dp[i-1][j-1]+(ll)abs(v[i]-j)*a[v[i]]);
            if(i>j)dp[i][j]=max(dp[i][j],dp[i-1][j]+(ll)abs(v[i]-(n-i+j+1))*a[v[i]]);
        }
    }
    cout<<*max_element(dp[n],dp[n]+1+n)<<endl;

    return 0;
}

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

using namespace std;

int main(void){
	char S[110];
	cin >> S;
	int len = strlen(S);
	int i;
	int ans = 0;
	for(i = 0; i*2 < len; i++){
		if(S[i] != S[len-i-1]){
			//cout<<"S["<<i<<"] = "<<S[i]<<"  S["<<len - i<<"] = "<<S[len-i]<<endl;
			ans++;
		}
	}
	//cout << "len = "<< len << endl;
	cout<<ans<<endl;

	
	
	return 0;
}




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

map<char, char> win;

int main() {
  int n, k;
  string t;
  map<char, int> p;
  cin >> n >> k >> p['r'] >> p['s'] >> p['p'];
  cin >> t;

  win['r'] = 'p';
  win['s'] = 'r';
  win['p'] = 's';

  ll ans = 0;
  string u(n, '-');
  for (int i = 0; i < k; i++) {
    char w = win[t[i]];
    ans += p[w];
    u[i] = w;
  }

  for (int i = k; i < n; i++) {
    char w = win[t[i]];
    if (w != u[i - k]) {
      ans += p[w];
      u[i] = w;
    }
  }
  cout << ans << endl;
}


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

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

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

//ori
#define MOD 1000000007
 
int main() {
  int x;
  cin >> x;
  if(x<1200) cout << "ABC" << endl;
  else cout << "ARC" << endl;
  return 0;
}

Measured memory_bytes: 764
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#define rep(i, n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
int main(void) {
  int a, b;
  cin >> a >> b;
  if(a > b)
    swap(a, b);
  int k = 1;
  int ans = 0;
  rep(i, b) {
    ans += a * k;
    k *= 10;
  }
  cout << ans << endl;
  return 0;
}

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

int main() {
  int a,b,c,d,e,f;
  cin>>a>>b>>c;
  d=max(a,max(b,c));
  e=a+b+c-max(a,max(b,c))-min(a,min(b,c));
  f=min(a,min(b,c));
  cout<<d*10+e+f<<endl;
}

Measured memory_bytes: 256
#include <stdlib.h>
#include <cmath>
#include <cstdio>
#include <cstdint>
#include <string>
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
using namespace std;
using ll = long long;

int main(){
  int N,Q;
  cin >> N;
  vector<int> A(N);
  vector<int> count(100001,0);
  ll sum=0;
  for(int i=0;i<N;i++){
    cin >> A.at(i);
    sum+=A.at(i);
    count.at(A.at(i))++;
  }
  
  cin >> Q;
  int B,C;
  for(int i=0;i<Q;i++){
    cin >> B >> C;
    sum=sum+(C-B)*count.at(B);
    count.at(C)+=count.at(B);
    count.at(B)=0;
    printf("%lld\n",sum);
  }

  return 0;
}


Measured memory_bytes: 4044
#define _USE_NATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
#include <random>
#include <tuple>


using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
#define EPS 1e-9
const int INF = 1050000000;
const long long LINF = 1LL << 60;
const ll MOD = 1e9 + 7;
const int MINF = -1050000000;

int main() {
	string s;
	cin >> s;
	int tmp=0;
	
	int a = s[0] - '0', b = s[1] - '0', c = s[2]- '0', d=s[3]-'0';
	if (a + b + c + d == 7) cout << a << "+" << b << "+" << c << "+" << d << "=" << 7;
	else if(a + b + c - d == 7)cout << a << "+" << b << "+" << c << "-" << d << "=" << 7;
	else if(a + b - c + d == 7) cout << a << "+" << b << "-" << c << "+" << d << "=" << 7;
	else if(a + b - c - d==7) cout << a << "+" << b << "-" << c << "-" << d << "=" << 7;
	else if(a - b + c + d==7) cout << a << "-" << b << "+" << c << "+" << d << "=" << 7;
	else if(a - b + c - d==7)cout << a << "-" << b << "+" << c << "-" << d << "=" << 7;
	else if(a - b - c + d==7)cout << a << "-" << b << "-" << c << "+" << d << "=" << 7;
	else if(a - b - c - d==7)cout << a << "-" << b << "-" << c << "-" << d << "=" << 7;
	return 0;
}


Measured memory_bytes: 256
S, T = input(), input()
if len(T) > len(S):
    print('UNRESTORABLE')
    exit()

able_list = []

for i in range(len(S) - len(T) + 1):
    S_part = S[i:len(T) + i]
    for j in range(len(T)):
        if S_part[j] == T[j] or S_part[j] == '?':
            if j == len(T) - 1:
                able_list.append(S[0:i] + T + S[len(T) + i:])
            continue
        else:
            break

if not able_list:
    print('UNRESTORABLE')
    exit()

for i in range(len(able_list)):
    able_list[i] = able_list[i].replace('?', 'a')

able_list.sort()
print(able_list[0])

Measured memory_bytes: 3064
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
const int MAX_N = 100000;
ll fact[MAX_N + 1];
int main(){
	ll ans;
	fact[0] = 0;
	fact[1] = 1;
	ll fs = 1;
	for (int i = 2; i < MAX_N + 1; i++){
		fs = (fs*i) % MOD;
		fact[i] = (fact[i-1] + fs) % MOD;
	}
	while (1){
		int N, R;
		scanf("%d", &N);
		if (N == 0) break;
		vector<int> word(N);
		for (int i = 0; i < N; i++) word[i] = i;
		word.push_back(0);
		ans = 0;
		scanf("%d", &R);
		vector<int> s(2*R+2, 0);
		s[2 * R + 1] = N;
		for (int i = 0; i < R; i++){
			scanf("%d%d", &s[i], &s[i+R]);
			s[i]--; s[i+R]--;
			s.push_back(s[i] + 1);
			s.push_back(s[i+R] + 1);
			swap(word[s[i]], word[s[i+R]]);
		}
		sort(s.begin(), s.end());
		s.erase(unique(s.begin(), s.end()), s.end());
		for (int i = 0, R = s.size() - 1; i < R; i++){
			ll tmp = fact[N - s[i] - 1] - fact[N - s[i+1] - 1];
			tmp = (tmp * word[s[i]]) % MOD;
			ans =(ans + tmp) % MOD;
			int dif = s[i+1] - s[i];
			for (int j = i + 1; j < R; j++){
				word[s[j]] -= (word[s[j]] > word[s[i]] ? dif : 0);
			}
		}
		printf("%lld\n", (ans + MOD) % MOD);
	}
	return 0;
}

Measured memory_bytes: 2620
N=int(input())
A=list(map(int,input().split()))
import copy
li=[0]
ans=0

for j in range(N):
    ans+=A[j]
    li.append(copy.copy(ans))

li.sort()
ans=0
temp=1
for i in range(N):

    if li[i]==li[i+1]:
        temp+=1
    else:
        ans+=temp*(temp-1)//2
        temp=1
ans+=temp*(temp-1)//2
print(ans)


Measured memory_bytes: 30880
#include <bits/stdc++.h>
using namespace std;
    
#define IOS cin.sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i, n) for (int i = 0; i < n; i++)
#define repn(i, a, b) for (int i = a;i<=b;i++)
#define ll long long int
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define mem(x) memset(x, 0, sizeof(x))
#define ritr(it, a) for (auto it = a.begin(); it != a.end(); it++)
#define PI 3.1415926535897932384626
#define pai pair < int, int> ;
#define pal pair < ll, ll> ;
#define vi vector <int> ;
#define vl vector < ll > ;
#define vpai vector < pii > ;

const int mod = 1e9+7;
const int INF = INT_MAX;
const int sze = 3005;

int n;
int mat[25][25];
ll dp[21][1<<21];

ll calc(int start,int mask){
    
    if(start==n) return 1;
    if(mask==0) return 0;
    if(dp[start][mask]!=-1) return dp[start][mask];

    ll count=0;
    for(int i=0;i<n;i++){
        if(mask&(1<<i)&&mat[start][i]){
            count=(count+calc(start+1,mask^(1<<i)))%mod;
        }
    }

    return dp[start][mask]=count;
}

void solve() {
    cin>>n;
    rep(i,n) rep(j,n) cin>>mat[i][j];
    memset(dp,-1,sizeof(dp));

    cout<<calc(0,(1<<21)-1);
}

int main() {
    IOS;

    int t = 1;
    //cin >> t;
    while (t--) {
       solve();
    }

  return 0;
}

Measured memory_bytes: 347648
import fractions
a,b,c,d=map(int,input().split())
cdgcd=(c*d)//fractions.gcd(c,d)
print(b-(a-1)-(b//c) +((a-1)//c) -(b//d) +((a-1)//d) +(b//cdgcd) -(a-1)//cdgcd)

Measured memory_bytes: 5048
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
ll int dp[1000005];
ll int N,K;
vector<ll int> v;
int funct(int z)
{
  int x;
  if(z==N-1)
    return 0;
  if(z>=N)
    return 0;
  if(dp[z+1]==-1)
    dp[z+1]=funct(z+1);
  int mini=abs(v[z+1]-v[z])+dp[z+1];
  for(x=2;x<=K&&(z+x)<N;x++)
  {
    if(dp[z+x]==-1)
      dp[z+x]=funct(z+x);
   	mini=mini<=(abs(v[z+x]-v[z])+dp[z+x])?mini:(abs(v[z+x]-v[z])+dp[z+x]);
  }
  dp[z]=mini;
  return dp[z]; 
}
int main()
{
  int i,x;
  for(i=0;i<1000005;i++)
    dp[i]=-1;
  cin>>N>>K;
  for(i=0;i<N;i++)
  {
    cin>>x;
    v.pb(x);
  }
  dp[0]=funct(0);
  cout<<dp[0]<<endl;
  return 0;
}

Measured memory_bytes: 16756
//! Framework <https://github.com/vain0x/procon>

#![allow(non_snake_case)]
#![allow(unused_imports)]

use std::collections::*;

pub struct Scan(Box<dyn Iterator<Item = &'static str>>); // '

impl Scan {
    fn new() -> Self {
        let mut buf = String::new();
        let read_line = move || {
            std::io::stdin().read_line(&mut buf).unwrap();
            Box::leak(buf.split_off(0).into_boxed_str()).split_whitespace()
        };
        Scan(Box::new(std::iter::repeat_with(read_line).flatten()))
    }

    pub fn word<T: std::str::FromStr>(&mut self) -> T {
        self.0.next().unwrap().parse().ok().unwrap()
    }

    pub fn list<T: std::str::FromStr>(&mut self, len: usize) -> Vec<T> {
        std::iter::repeat_with(|| self.word()).take(len).collect()
    }
}

fn main() {
    let mut scan = Scan::new();

    let N = scan.word::<usize>();
    let mut name = Vec::new();
    let mut x = N - 1;
    loop {
        name.push((b'a' + (x % 26) as u8) as char);
        if x < 26 {
            break;
        }

        x /= 26;
        x -= 1;
    }
    name.reverse();
    let name = name.into_iter().collect::<String>();
    println!("{}", name);
}


Measured memory_bytes: 2148
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <stack>
#include <numeric>
#include <algorithm>
#include <bitset>
#include <complex>
#include <iomanip>

using namespace std;
typedef long long ll;
typedef long long int llint;
#define MM 1000000000
#define MOD MM+7
#define pi pair<int,int>
#define pl pair<ll,ll>
#define chmax(a,b) (a<b ? a=b:0)
#define chmin(a,b) (a>b ? a=b:0)
#define INF (1 << 29) //536870912
const long double PI = acos(-1);
int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};
int GCD(int x,int y){
    return y ? GCD(y,x%y) : x;
}
vector<int> g[100010];
int h[100010];
int x,y;
int main(){
    while(true){
        cin >> x >> y;
        if(x == 0&& y == 0){
            break;
        }
        cout << min(x,y) << " " << max(x,y) << endl;
    }
}





Measured memory_bytes: 5348
import sys
from sys import exit
from collections import deque
from bisect import bisect_left, bisect_right, insort_left, insort_right #func(リスト,値)
from heapq import heapify, heappop, heappush
from math import *

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)

N,Y = mint()

for a in range(N+1):
    for b in range(N-a+1):
        c = N-a-b
        if 10000*a+5000*b+1000*c==Y:
            print(a,b,c)
            exit()
print(-1,-1,-1)

Measured memory_bytes: 68960
import sys
from collections import deque, defaultdict
import copy
import bisect
#sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import combinations, permutations

import sys
def input():
	return sys.stdin.readline().strip()

N, M = list(map(int, input().split()))

graph = [[] for _ in range(N)]
graph2 = [-1 for _ in range(N)]
for i in range(M):
	a, b = list(map(int, input().split()))
	a -= 1
	b -= 1
	graph[a].append(b)
	graph[b].append(a)

que = deque([])
que.append(0)
graph2[0] = 0
nibu = 1

num01 = dict()
num01[0] = 1
num01[1] = 0

while len(que) > 0:
	node = que.popleft()
	for edge in graph[node]:
		if graph2[edge] == -1:
			graph2[edge] = (graph2[node] + 1) % 2
			que.append(edge)
			num01[graph2[edge]] += 1
		elif graph2[node] == graph2[edge]:
			nibu = 0

if nibu == 0:
	print(N*(N-1)//2 - M)
else:
	print(num01[0]*num01[1] - M)

Measured memory_bytes: 59184
//Code is like humor. When you have to explain it, it’s bad.
#define fastio ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#include <bits/stdc++.h>
#define MOD 1000000007
#define MOD1 998244353
#define endl "\n"
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define mkp make_pair
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define forn(i, n) for(int i = 0; i < int(n); i++)
#define forn1(i, n) for(int i = 1; i <= int(n); i++)
#define int ll
using namespace std;
typedef long double ld;
typedef long long ll;
typedef set <int> si;
typedef multiset <int> msi;
typedef unordered_set <int> usi;
typedef unordered_multiset <int> umsi;
typedef pair<int,int> pairs;
typedef vector <int> VI;
typedef map<int,int> mii;
typedef multimap <int,int> mmii;
typedef unordered_map <int,int> umii;
typedef unordered_multimap<int,int> ummii;
double pi = 2 * acos(0.0);
inline int two(int n) { return 1 << n; }
struct cmp{
    /////call by set<pair<int, int>, cmp>
    bool operator() (const pair<int, int>& a, const pair<int, int>& b) const{
        int lena= a.second - a.first + 1;
        int lenb = b.second - b.first + 1;
        if(lena == lenb) return a.first < b.first;
        return lena > lenb;
    }
};
bool isPrime(int n) { 
    if (n <= 1)  return false; if (n <= 3)  return true; if (n%2 == 0 || n%3 == 0) return false; 
    for (int i=5; i*i<=n; i=i+6) if (n%i == 0 || n%(i+2) == 0) return false; 
    return true; 
}

const int N = 1e18;

int index(int n) {
    int t = 0;
    n/=10;
    while(n) {
        n/=10;
        t++;
    }
    return t;
}

signed main()  {
    fastio;
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
    #endif 
    //
    int t=1;
    //cin>>t;
    while(t--) {
        int n;
        cin>>n;
        bool b = false;
        VI vec(n);
        forn(i,n) {
            cin>>vec[i];
            if(vec[i] == 0) b = true;
        }
        if(b) {cout << "0\n";return 0;}

        int prod = 1;
        forn(i,n) {
            int i1 = index(prod);
            int i2 = index(vec[i]);
            if(i1+i2 > 18) {
                cout << "-1\n";
                return 0;
            }  
            prod *= vec[i];
            if(prod > N || prod <= 0) {
                cout << "-1\n";
                return 0;
            }
        }
        cout << prod << endl;
    }
    
    return 0;
}

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

int N, M, K;

void solve()
{
	for(int r=0;r<=N;++r)for(int c=0;c<=M;++c){
		int cnt = c*N+r*(M-c)-r*c;
		if(cnt == K){
			cout << "Yes\n";
			return;
		}
	}
	cout << "No\n";
}

int main()
{
	cin >> N >> M >> K;
	solve();
	return 0;
}

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

int main() {
    int n; cin >> n;
    if(n==1){
        cout << "Hello World" << endl;
    }
    else if(n==2){
        int a, b; cin >> a >> b;
        cout << a+b << endl;
    }
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.Closeable;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.StringTokenizer;
 
public class Main {
	
	public static final long dfs(long fst, long snd){
		final long max = Math.max(fst, snd);
		final long min = Math.min(fst, snd);
		//System.out.println(max + " " + min);
		
		if(max % min == 0){
			return 2 * (max / min * min) - min;
		}else{
			return 2 * (max / min * min) + dfs(min, max % min);
		}
	}
	
	public static void main(String[] args) throws IOException {
		final Scanner sc = new Scanner(System.in);
		
		final long N = sc.nextLong();
		final long X = sc.nextLong();
		
		System.out.println(N + dfs(X, N - X));
	}
 
	public static class Scanner implements Closeable {
		private BufferedReader br;
		private StringTokenizer tok;
 
		public Scanner(InputStream is) throws IOException {
			br = new BufferedReader(new InputStreamReader(is));
		}
 
		private void getLine() throws IOException {
			while (!hasNext()) {
				tok = new StringTokenizer(br.readLine());
			}
		}
 
		private boolean hasNext() {
			return tok != null && tok.hasMoreTokens();
		}
 
		public String next() throws IOException {
			getLine();
			return tok.nextToken();
		}
 
		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
 
		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}
 
		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}
 
		public void close() throws IOException {
			br.close();
		}
	}
}

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

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

int main() {
	int N;
	cin >> N;
	vector<P> v(N);
	for (int i = 0; i < N; ++i) {
		ll a, b;
		cin >> a >> b;
		v[i] = P(b, a);
	}
	sort(v.rbegin(), v.rend());

	ll t = 1e18;
	for (int i = 0; i < N; ++i) {
		t = min(t, v[i].first);
		t -= v[i].second;
	}

	if (t >= 0) { cout << "Yes" << endl; }
	else { cout << "No" << endl; }

	return 0;
}


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

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

   int a[n],b[n],c[n];
   for(int i=0;i<n;i++) cin>>a[i]>>b[i]>>c[i];

   int dp[n][3];	
   
   dp[0][0] = a[0];
   dp[0][1] = b[0];
   dp[0][2] = c[0];

   for(int i=1;i<n;i++){
   	   dp[i][0] = a[i] + max(dp[i-1][1],dp[i-1][2]);
   	   dp[i][1] = b[i] + max(dp[i-1][0],dp[i-1][2]);
   	   dp[i][2] = c[i] + max(dp[i-1][0],dp[i-1][1]);
   }

   int res = max(dp[n-1][0], max(dp[n-1][1],dp[n-1][2]));

   cout<< res;
 return 0;   
}

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

#define MAX_SIZE 110
#define INF (1<<30)
#define NOT_VISITED 0
#define VISITED 1
#define COMPLETE 2

int n, G[MAX_SIZE][MAX_SIZE];
int d[MAX_SIZE], status[MAX_SIZE];

void dijkstra() {
    for (int i = 0; i < n; i++) {
        d[i] = INF;
        status[i] = NOT_VISITED;
    }
    d[0] = 0;

    int u, min_cost;
    while (1) {
        u = -1;
        min_cost = INF;
        for (int i = 0; i < n; i++) {
            if (min_cost > d[i] && status[i] != COMPLETE) {
                u = i;
                min_cost = d[i];
            }
        }
        if (u == -1) break;
        status[u] = COMPLETE;
        for (int i = 0; i < n; i++) {
            if (status[i] == COMPLETE || G[u][i] == INF) continue;
            if (d[i] > d[u] + G[u][i]) {
                d[i] = d[u] + G[u][i];
                status[i] = VISITED;
            }
        }
    }
    
    return;
}

void print() {
    for (int i = 0; i < n; i++) {
        cout << i << " ";
        if (d[i] == INF) cout << -1;
        else cout << d[i];
        cout << endl;
    }
    return;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            G[i][j] = INF;
        }
    }

    int u, k, v, c;
    for (int i = 0; i < n; i++) {
        cin >> u >> k;
        for (int j = 0; j < k; j++) {
            cin >> v >> c;
            G[u][v] = c;
        }
    }

    dijkstra();

    print();

    return 0;
}


Measured memory_bytes: 3132
#include <algorithm>
#include <bitset>
//#include <boost/multiprecision/cpp_int.hpp>
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstring>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <sstream>
#include <stdio.h>
#include <string>
#include <tuple>
#include <vector>
#include<iomanip>
// namespace mp = boost::multiprecision;
using namespace std;
using ull = unsigned long long;
using ld = long double;
// using ll = boost::multiprecision::cpp_int;
using ll = long long;
#define FOR(i, N) for(ll i = 0; i < N; ++i)

#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
// using int = ll;
ll gcd(ll m, ll n) {
    if(n == 0)
        return abs(m);
    return (gcd(n, m % n));
}
void putYN(bool b) {
    if(b) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}
void swap(ll &a, ll &b) {
    ll tmp = a;
    a = b;
    b = tmp;
}
ll combi(ll n, ll k) {
    ll r = 1, rr = 1;
    for(ll i = 0; i < k; ++i) {
        r *= (n - i);
        rr *= (i + 1);
        // r %= 1000000007;
        // rr %= 1000000007;
    }
    r /= rr;
    // r %= 1000000007;
    return r;
}
int main() {
  vector<string> a={"SUN","MON","TUE","WED","THU","FRI","SAT"};
  string s;
  cin>>s;
  cout<<distance(find(a.begin(),a.end(),s),a.end());
  
  return 0;
}


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

int main(){
  int n,x;
  cin >> n >> x;
  int l[n];
  int count = 1;
  int dist = 0;
  for(int i=0;i<n;i++){
    cin >> l[i];
    dist += l[i];
    if(dist<=x){
      count ++;
    }
  }
  cout << count << endl;
  return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define ll long long
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define pl pair<ll,ll>
#define rep(i,b) for(ll i=0;i<b;i++)

using namespace std;

int main() {
    std::cout<<std::fixed<<std::setprecision(10);
    ll N, K, L, R,mx=0,point;
    long double ans=0;
    cin >> N >> K;

    ll A[N+1]; A[0] = 0; // 1オリジン
    int P[N];
    rep(i, N) {
        cin >> P[i]; // input
        A[i+1]=P[i];
    }
    rep(i, N) A[i+1] += A[i]; // 累積和
    rep(i, N-K+1) {
        L=i+1;R=L+K-1;
        //cout << A[R] - A[L-1] << endl;
        if(mx<A[R]-A[L-1]){
            mx=A[R]-A[L-1];
            point=i;
        }
    }
    for(ll i=point;i<point+K;i++)ans+=double((P[i]+1)/2.0);
    cout<<ans<<endl;
}


Measured memory_bytes: 2560
#include <bitset>
#include <cmath>
#include <iostream>

using namespace std;
using ll = long long;

ll hoge(ll x) {
  bitset<64> bset;
  for (ll i = 0; i < 64; ++i) {
    ll a = pow(2LL, i);
    ll b = pow(2LL, i + 1);
    bset.set(i, ((x + 1) / b * a + max(0LL, (x+1) % b - a)) % 2);
  }
  return bset.to_ullong();
}

int main() {
  ll a, b;
  cin >> a >> b;
  cout << (hoge(a-1) ^ hoge(b)) << endl;
}

Measured memory_bytes: 4032
import java.util.Scanner;
import java.util.ArrayList;

public class Main {
	Scanner sc;
	public void run(){
		sc = new Scanner(System.in);
		while(sc.hasNextInt()){
			int n = sc.nextInt();
			if(n != 0){
				calc(n);
			}
			else{
				break;
			}
		}
	}
	public void calc(int n){
		int ps[] = new int[n+1];
		int ts[] = new int[n+1];
		for(int i = 1; i < n+1; i++){
			ps[i] = sc.nextInt();
			ts[i] = sc.nextInt();
		}
		
		int[][] memo = new int[n+1][4];
		for(int i = 0; i < n+1; i++){
			for(int j = 0; j < 4; j++){
				memo[i][j] = Integer.MAX_VALUE; 
			}
		}
		memo[0][1] = 0; 
		memo[0][2] = -1; 
		memo[0][3] = 1;
		
		boolean result = true;
		
		for(int i = 0; i < n; i++){
			int nextT = ts[i+1];
			int nextP = ps[i+1];
			int nowT = ts[i];
			int nowP = ps[i];
			for(int k = 1; k < 4; k++){
				if(memo[i][k] != -1) {
					//置いてから来る
					int needT = (k + 1) * nowP + nextP + nowT;
					int needP = nowP + nextP + memo[i][k];
					if(needT <= nextT && needP < memo[i+1][1]) {
						memo[i+1][1] = needP;
					}
					//置かない
					if(k != 3){
						needT = (k + 1) * Math.abs(nowP - nextP) + nowT;
						needP = Math.abs(nowP - nextP) + memo[i][k];
						if(needT <= nextT && needP < memo[i+1][k+1]){
							memo[i+1][k+1] = needP;
						}
					}
				}
						
			}
			for(int k = 1; k < 4; k++){
				if(memo[i+1][k] == Integer.MAX_VALUE){
					memo[i+1][k] = -1;
				}
			}
			
			if(memo[i+1][1] == -1 && memo[i+1][2] == -1 && memo[i+1][3] == -1){
				System.out.println("NG " + (i+1));
				result = false;
				break;
			}
		}
		
		if(result){
			int min = Integer.MAX_VALUE;
			for(int k = 1; k < 4; k++){
				if(memo[n][k] != -1){
					int dis = memo[n][k] + ps[n];
					if(dis < min) min = dis;
				}
			}
			System.out.println("OK " + min);
		}
	}
	public static void main(String[] args){
		new Main().run();
	}
}

Measured memory_bytes: 25348
/* ABC151 D - Maze Master */
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
#include <numeric>

using namespace std;

/*-----------------------------------------------------------------------------
　定義
 -------------------------------------------------------------------------------*/
#define ALL(x)					(x).begin(),(x).end()
#define REP(i, n)				for (int (i) = 0 ; (i) < (ll)(n) ; ++(i))
#define REPN(i, m, n)			for (int (i) = m ; (i) < (ll)(n) ; ++(i))
#define INF						(int)2e9
#define MOD						(1000 * 1000 * 1000 + 7)
#define Ceil(x, n)				(((((x))+((n)-1))/n))		/* Nの倍数に切り上げ割り算 */
#define CeilN(x, n)				(((((x))+((n)-1))/n)*n)		/* Nの倍数に切り上げ */
#define FloorN(x, n)			((x)-(x)%(n))				/* Nの倍数に切り下げ */
#define IsOdd(x)				(((x)&0x01UL) == 0x01UL)			
#define IsEven(x)				(!IsOdd((x)))						
#define M_PI					3.14159265358979323846
typedef long long				ll;
typedef pair<int, int>			P;

/*-----------------------------------------------------------------------------
　定義
 -------------------------------------------------------------------------------*/
const int step[4][2] = {
	{1, 0},
	{-1, 0},
	{0, 1},
	{0, -1},
};

/*-----------------------------------------------------------------------------
　処理
 -------------------------------------------------------------------------------*/
int H, W;
char HW[50 + 1][50 + 1];

// bfs
int bfs(int sx, int sy, int gx, int gy)
{
	vector<vector<int>> dist(H, vector<int>(W, INF));

	// 開始位置で初期化
	queue<P> que;
	que.push(P{sx, sy});
	dist[sx][sy] = 0;

	// 全てへの距離
	while (que.size()) {
		P now = que.front();
		que.pop();
		//if ((now.first == gx)&&(now.second == gy)) {
		// 	break;
		//}
		for (int i = 0; i < 4; i++) {
			int xNext = now.first + step[i][0];
			int yNext = now.second + step[i][1];
			if (!((0 <= xNext && xNext < H) && (0 <= yNext && yNext < W))) {
				continue;
			}
			char nextPos = HW[xNext][yNext];
			if ((dist[xNext][yNext] == INF) && (HW[xNext][yNext] != '#')) {
				dist[xNext][yNext] = dist[now.first][now.second] + 1;
				que.push(P{xNext, yNext});
			}
		}
	}

	return dist[gx][gy];
}

// メイン
int main()
{
	// 入力
	cin >> H >> W;
	REP(i, H) REP(j, W) cin >> HW[i][j];

	// dfs
	int res = bfs(0, 0, H - 1, W - 1);

	// 結果
	int whileCnt = 0;
	REP(i, H) {
		REP(j, W) {
			if (HW[i][j] == '.') whileCnt++;
		}
	}

	if (res == INF) {
	 	cout << -1 << endl;
	} else {
	 	cout << whileCnt - res - 1 << endl;
	}
	return 0;
}

Measured memory_bytes: 384