akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define For(i,a,b) for(i=a;i<b;i++)
#define pb push_back
#define vi vector<int>
#define vii vector<vector<int>>
#define vll vector<long long>  
#define vd vector<double>
#define pi (int,int)
#define vpi vector<pair<int,int>>
#define vs vector<string>
#define mp make_pair
#define ll long long
#define vc vector<char>
#define rng(x) x.begin(),x.end()
#define B(x) x.begin()
#define E(x) x.end()
#define F first
#define S second
#define me max_element
#define ne min_element
#define LL "%I64d"
#define pi 3.1415926536
using namespace std;
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  
  ll n,sum=0,i;
  cin>>n;
  vll a(n);
  For(i,0,n) cin>>a[i];
  For(i,0,n-1)
  {
    if(a[i]>a[i+1])
    {
      sum+=a[i]-a[i+1];
      a[i+1]+=(a[i]-a[i+1]);
    }
  }
  cout<<sum<<"\n";
  return 0;
}
 

        

Measured memory_bytes: 4780
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <string>
#include <queue>
#include <unordered_map>
#include <iterator>
#include <stack>
#include <unordered_set>
#include <iomanip>
#include <ctime>
#include <cstring>
#include <bitset>

#include <random>
#define all(x) (x).begin(), (x).end()


using namespace std;
void dout() { cerr << endl; }
typedef long long ll;
template <typename Head, typename... Tail>
void dout(Head H, Tail... T) {
    cerr << H << ' ';
    dout(T...);
}

using ll = long long;
using pii = pair<ll, ll>;
using ld = long double;
using pll = pair<long long, long long>;

void precalc() {}
template <typename T>
void do_uniq(vector<T> vec){
    sort(all(vec));
    vec.resize(unique(all(vec)) - vec.begin());
}

#define solvsh
//#define multi
#ifdef solvsh


const int MAXN = 1e5 + 29;

void solve() {
    vector<int> seq = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
    int k;
    cin >> k;
    cout << seq[k - 1];
}

#else
const int MAXN = 2 *  50005;

const int h = 7;

int dp[h][h][h][h];

void solve() {



}
#endif

void multisolve() {
    int t;
    cin >> t;

    while (t--)
        solve();
}

void gen(){
    cout << "100000 99999\n";

    for (int i = 0; i < 99999; ++i) {
        cout << 1 << " " << 2 + i << "\n";
    }
}

#define int int
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cout << fixed << setprecision(20);

#ifdef multi
    multisolve();
#else
    precalc();
    solve();
//    gen();
#endif

#ifdef LOCAL
    //cout << '\n' << (double)clock() / CLOCKS_PER_SEC << '\n';
#endif
}

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc =new Scanner(System.in);
		String s =sc.nextLine();
		
		char[] c=s.toCharArray();
		if(c.length==26) {
			for(int i=24;i>=0;i--) {
				char[] d=String.copyValueOf(c, i, c.length-i).toCharArray();
				Arrays.sort(d);
				for(int j=0;j<d.length;j++) {
					if(c[i]<d[j]) {
						String ans="";
						for(int k=0;k<i;k++) {
							ans=ans+String.valueOf(c[k]);
						}
						ans=ans+String.valueOf(d[j]);
						System.out.println(ans);
						return;
						
					}
				}
			}
			System.out.println(-1);
			return;
		}
		
		else {
			char x=(char)('a'-1);
			LOOP:while(x<='z'){
				x=(char) (x+1);
				for(int i=0;i<c.length;i++) {
					if(x==c[i]) {
						continue LOOP;
					}
				}
				s=s+String.valueOf(x);
				System.out.println(s);
				return;
				
			}
		}
		
		
		
	}

}


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

ll dp[100010]={0};

int main(){

    ll n,w;
    cin>>n>>w;
    ll arr[n][2];
    rep(i,0,n){
        rep(j,0,2){
            cin>>arr[i][j];
        }
    }
    rep(i,0,n){
        for(ll j=w;j>=1;j--){
            if(j+arr[i][0]<=w && dp[j]){
                if(dp[j+arr[i][0]]<(arr[i][1]+dp[j])){
                    dp[j+arr[i][0]]=arr[i][1]+dp[j];
                }
            }
        }
        if(arr[i][1]>dp[arr[i][0]])dp[arr[i][0]]=arr[i][1];
    }
    ll mx=0;
    rep(i,1,w+1)if(dp[i]>mx)mx=dp[i];
    cout<<mx<<endl;
    
    return 0;
}

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

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

  vector<int> card(N);
  for(int i = 0; i < N; i++){
    cin >> card.at(i);
  }
  sort(card.begin(), card.end());
  reverse(card.begin(), card.end());

  int A = 0, B = 0;
  for(int i = 0; i < N; i++){
    int d;
    d = i % 2;
 
    if(d == 0){
      A += card.at(i);
    }
    else{
      B += card.at(i);
    }
  }

  cout << A - B << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
#include<complex>
#include<numeric>
using namespace std;

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
constexpr ll mod = 1000000009;
const ll INF = mod * mod;
typedef pair<int, int>P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
typedef pair<ll, ll> LP;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-12;
const ld pi = acos(-1.0);


struct modint {
	ll n;
	modint() :n(0) { ; }
	modint(ll m) :n(m) {
		if (n >= mod)n %= mod;
		else if (n < 0)n = (n%mod + mod) % mod;
	}
	operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
modint operator+=(modint &a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= mod; return a; }
modint operator-=(modint &a, modint b) { a.n -= b.n; if (a.n < 0)a.n += mod; return a; }
modint operator*=(modint &a, modint b) { a.n = ((ll)a.n*b.n) % mod; return a; }
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, int n) {
	if (n == 0)return modint(1);
	modint res = (a*a) ^ (n / 2);
	if (n % 2)res = res * a;
	return res;
}

ll inv(ll a, ll p) {
	return (a == 1 ? 1 : (1 - p * inv(p%a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }

const int max_n = 1 << 18;
modint fact[max_n], factinv[max_n];
void init_f() {
	fact[0] = modint(1);
	for (int i = 0; i < max_n - 1; i++) {
		fact[i + 1] = fact[i] * modint(i + 1);
	}
	factinv[max_n - 1] = modint(1) / fact[max_n - 1];
	for (int i = max_n - 2; i >= 0; i--) {
		factinv[i] = factinv[i + 1] * modint(i + 1);
	}
}
modint comb(int a, int b) {
	if (a < 0 || b < 0 || a < b)return 0;
	return fact[a] * factinv[b] * factinv[a - b];
}
modint combP(int a, int b) {
	if (a < 0 || b < 0 || a < b)return 0;
	return fact[a] * factinv[a - b];
}


void solve() {
	int n, k; cin >> n >> k;
	vector<int> a(n,0);
	rep(i, n)cin >> a[i];
	rep(i, k) {
		vector<int> cnt(n + 1);
		rep(j, n) {
			int le = j - a[j]; if (le < 0)le=0;
			int ri = j + a[j]; if (ri >= n)ri = n - 1;
			cnt[le]++; cnt[ri + 1]--;
		}
		rep(j, n) {
			cnt[j + 1] += cnt[j];
			a[j] = cnt[j];
		}

		bool fin = true;
		rep(j, n)if (a[j] < n)fin = false;
		if (fin) {
			break;
		}
	}
	rep(i, n) {
		if (i > 0)cout << " ";
		cout << a[i];
	}
	cout << "\n";
}


signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
    //cout << fixed << setprecision(6);
	//init_f();
	//init();
	//int t; cin >> t;rep(i,t)
	solve();
	stop
		return 0;
}


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

int main() {
    while (1) {
        string s;
        cin >> s;
        if (s == "#")
            break;

        int y, m, d;
        cin >> y >> m >> d;

        if (y >= 31) {
            if (y == 31 && m <= 4)
                ;
            else{
                s = "?";
                y -= 30;
            }
        }

        cout << s << " " << y << " " << m << " " << d << "\n";
    }

    return 0;
}


Measured memory_bytes: 3056
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define REP(i,a,b) for (int i = a; i <b; i++)
typedef long long ll;
#define int ll
typedef vector<int> vi;
typedef vector<long long> vl;
typedef pair<int,int> pi;
#define trace(x) cout<<#x<<"="<<x<<"\n";
#define sz(x) (int)(x.size())
#define mod 1000000007
#define endl "\n"
template < typename F, typename S >
ostream& operator << ( ostream& os, const pair< F, S > & p ) {
    return os << "(" << p.first << ", " << p.second << ")";
}

template < typename T >
ostream &operator << ( ostream & os, const vector< T > &v ) {
    os << "{";
    typename vector< T > :: const_iterator it;
    for( it = v.begin(); it != v.end(); it++ ) {
        if( it != v.begin() ) os << ", ";
        os << *it;
    }
    return os << "}";
}

template < typename T >
ostream &operator << ( ostream & os, const set< T > &v ) {
    os << "[";
    typename set< T > :: const_iterator it;
    for ( it = v.begin(); it != v.end(); it++ ) {
        if( it != v.begin() ) os << ", ";
        os << *it;
    }
    return os << "]";
}

template < typename F, typename S >
ostream &operator << ( ostream & os, const map< F, S > &v ) {
    os << "[";
    typename map< F , S >::const_iterator it;
    for( it = v.begin(); it != v.end(); it++ ) {
        if( it != v.begin() ) os << ", ";
        os << it -> first << " = " << it -> second ;
    }
    return os << "]";
}

#define deb(x) cerr << #x << " = " << x << endl;



int32_t main(){
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    vi a(n);
    int sum=0;
    REP(i,0,n){
        cin>>a[i];
        sum+=a[i];
    }
    sum=sum/n;
    int ans=0;
    REP(i,0,n){
        ans+=(a[i]-sum)*(a[i]-sum);
    }
    int ans1=0;
    sum++;
     REP(i,0,n){
        ans1+=(a[i]-sum)*(a[i]-sum);
    }
    ans=min(ans,ans1);
    sum=sum-2;
    ans1=0;
    sum++;
     REP(i,0,n){
        ans1+=(a[i]-sum)*(a[i]-sum);
    }
    ans=min(ans,ans1);
    cout<<ans<<"\n";


    return 0;
}

Measured memory_bytes: 256
n = int(input())
s = list(input() for i in range(n))
a = s.count("AC")
w = s.count("WA")
t = s.count("TLE")
r = s.count("RE")

print("AC x " + str(a))
print("WA x " + str(w))
print("TLE x " + str(t))
print("RE x " + str(r))

Measured memory_bytes: 78436
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main() {
	unsigned long long N, K;
	cin >> N >> K;

	unsigned long long n1 = N / K;

	if(K%2==0) {
		unsigned long long n2 = n1 + (N%K >= K/2 ? 1 : 0);
		cout << n1*n1*n1+n2*n2*n2 << endl;
	} else {
		cout << n1*n1*n1 << endl;
	}
}


Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws Exception {
		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();	
		}
		Arrays.sort(a);
		System.out.println(a[N - 1] - a[0]);
		sc.close();
	}
}

Measured memory_bytes: 23764
#include <bits/stdc++.h>
#include<vector>
using namespace std;
#define rep(i, n)        for(int i=0; i<(int)(n); ++i)
int main() {
  string a;cin>>a;
  int b=0,c=0;
  rep(i,a.size()){
    if(a[i]=='0')b++;
    else c++;
  }
  cout<<min(b,c)*2;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
#include<cctype>
using namespace std;
#define rep(i,n) for (int i=0;i<(n);i++)
#define all(v) (v).begin(),(v).end()
typedef long long int ll;
#define pi 3.1415926535897932384
#define E9 1000000000
#define eps 1e-4
#define pii pair<int,int>

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

int main(){
  ll N, P; cin >> N >> P;
  map<ll,int> ret = prime_factor(P);
  ll retval = 1;
  for (auto p:ret){
    ll tmp = 1; rep(i,p.second/N) tmp *= p.first;
    retval *= tmp;
  }
  cout << retval << endl;

  // cout << fixed << setprecision(10);
  
  return 0;
}


Measured memory_bytes: 3612
#include <iostream>
#include <algorithm>
#include <cmath>
#include <limits>
#include <vector>
using namespace std;
using ll = long long;
int dp[101]={0};

int fun(int t) {
  dp[t]=(t+(t+1))/2;
  return dp[t];
}

int main (void) {
  int a,b,c;
  int ans=0;
  cin >> a>> b >> c;
  int m=a%b;
  for (int i=1; i<=100;i++) {
    if ((m*fun(i))%b==c){
      cout << "YES";
      return 0;
    }
  }
  cout << "NO";
}

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

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;
typedef vector<int> vi;

int main(){
    string str;
    string str2 = "";
    cin >> str;
    for(int i=0;i<str.size();++i){
        if(i<str.size()-1 and str[i]=='B' and str[i+1]=='C') str2.push_back('D'), i++;
        else str2.push_back(str[i]);
    }
    //cout << str2 << endl;
    ll ans = 0, count = 0;
    for(int i=0;i<str2.size();++i){
        if(str2[i]=='B' or str2[i]=='C') count = 0;
        else if(str2[i]=='D') ans += count;
        else count++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 776
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#define rep(i,a,n) for(ll i =(a);i<(n);i++)
#define urep(i,a,n) for(ll i = (a);i>=(n);i--)
#define all(x) (x).begin(),(x).end()
#define INF 1e30
const int mod = 1e9 + 7;
typedef long long ll;
using namespace std;
ll dx[4] = { 1,-1,0,0 };
ll dy[4] = { 0,0,1,-1 };
ll N, M, Q, H, W, D, L, R, K, X, A, B, C, Z;
ll ans;
string S;
ll x[100000000];
ll y[100000000];
ll nowcost = 1;
ll gcd(ll a, ll b) {
	if (b == 0)return a;
	else return gcd(b, a%b);
}
ll DP[1000001];
int main() {
	string s[1000];
	cin>>N>>L;
	rep(i,0,N){
		cin>>s[i];
	}
	sort(s,s+N);
	rep(i,0,N){
		cout<<s[i];
	}
	cout<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>

int main (){
    int temp;
    unsigned long n;
    unsigned long i,j;
    unsigned long ans;

    temp = scanf("%lu", &n);
    i=(unsigned long)sqrt((double)n);

    while (i>0) {
        ans = n/i;
        if (n==i*ans){
            j=ans;
            break;
            
        }
        i--;
    }
    printf("%lu", i+j-2);
    
    return 0;
}


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

using namespace std;

const int MAXN = 1e5 + 10;
const int MOD = 1e9 + 7;
vector< int > gr[MAXN];
int dp[MAXN][2];

void dfs(int node, int boss) {
	int cntTotal = 1;
	int cntWhite = 1;
	for(auto &x : gr[node]) {
		if(x == boss) continue;
		dfs(x, node);
		cntTotal = (1ll*cntTotal*(dp[x][0] + dp[x][1])) % MOD;
		cntWhite = (1ll*cntWhite*(dp[x][0])) % MOD;
	}

	dp[node][1] = cntWhite;
	dp[node][0] = cntTotal;
}
int main() {
    #ifdef BLAT
        freopen("input", "r", stdin);
    #endif


    int n;
    cin >> n;

    for(int i = 1; i < n; ++i) {
    	int a, b;
    	cin >> a >> b;

    	gr[a].emplace_back(b);
    	gr[b].emplace_back(a);
    }

    dfs(1, 0);

    cout << (dp[1][0] + dp[1][1]) % MOD << '\n';
}   	

Measured memory_bytes: 13440
class Node:
  def __init__(self, id, children):
    self.id = id
    self.children = children
    self.type = "root"
    self.parent = None
    self.depth = 0

  def set_parent(self, parent):
    self.parent = parent
    self.type = "leaf" if len(self.children) == 0 else "internal node"

  def get_depth(self):
    if self.depth: return self.depth
    if self.type == "root": return 0
    self.depth = self.parent.get_depth() + 1
    return self.depth

  def display(self):
    print("node {}: parent = {}, depth = {}, {}, {}".format(
      self.id,
      self.parent.id if self.parent else -1,
      self.get_depth(),
      self.type,
      self.children
      )
    )

nodelist = {}
for i in range(int(input())):
  p = input().split()
  id = int(p[0])
  nodelist[id] = Node(id, list(map(int, p[2:])) if len(p) >= 3 else [])

for i in nodelist:
  n = nodelist[i]
  for cid in n.children:
    nodelist[cid].set_parent(n)

for i in sorted(nodelist): nodelist[i].display()

Measured memory_bytes: 56028
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
int main(){
  int N; cin >> N;
  vector<int> Xs(N);
  vector<int> Ys(N);
  double sum = 1;
  for(int i = 0; i < N;i++){
    sum *= (i+1);
    cin >> Xs[i] >> Ys[i];
  }
  double M = sum  / N;
  double ans = 0;
 
  for(int i = 0; i < N;i ++){
    
    double avr = 0;
    for(int j = 0; j < N ; j++){
      if(i != j){
        double dX = (Xs[i] - Xs[j]) ;
        double dY = (Ys[i] - Ys[j]) ;
        avr += sqrt(dX * dX + dY * dY) ;
      }
    }
    ans += avr * M ;
  }
  
  cout << setprecision(20) << ans / sum;
  
  return 0;
}

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


int main() {
  
  int N; //候補地数
  cin >> N;
  int T; //気温基準値
  cin >> T;
  int A; //目標気温
  cin >> A;
  vector<int> H(N); //標高
  for(int i = 0; i < N; i++) cin >>  H[i];
  
  int best_tempture = 3000000; //1<<30;
  int ans_num = 0;
  bool initialize = false;
  
  for(int i = 0 ; i < N ; i++){
    
     int tmp = (T*1000 - H[i]*6) - (A * 1000);
    if(tmp < 0) tmp = -tmp;
    if(best_tempture > tmp) best_tempture = tmp,ans_num = i;
    
    
    
  }
  
  cout << ans_num + 1 << endl;

  
 
}


           

Measured memory_bytes: 256
#include <stdio.h>

int cnt[200005];

int main() {
    int n; scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        int tt; scanf("%d", &tt);
        cnt[tt]++;
    }
    for (int i = 1; i <= n; i++)
        printf("%d\n", cnt[i]);
}


Measured memory_bytes: 2504
#include <iostream>
#include <stdio.h>
#include <string>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <queue>
#include <bits/stdc++.h>
#include <stack>
#include <vector>
#include <list>

using namespace std;

int main(){
  int a[3];
  int flag = 1;
  for(int i = 0; i < 3; i++)
    a[i] = 0;
  for(int i = 0; i < 3; i++){
    int x;
    cin >> x;
    if(x==5){
      if(a[0]!=1)
        a[0] = 1;
      else if(a[2]!=1)
        a[2] = 1;
      else
        flag = 0;
    }
    else if(x == 7){
      if(a[1]!=1)
        a[1] = 1;
      else
        flag = 0;
    }
    else
      flag = 0;
  }
  if(flag)
    cout << "YES" << endl;
  else
    cout << "NO" << endl;

  return 0;
}

Measured memory_bytes: 256
h,w = map(int, input().split())
A = []
for i in range(h):
    s = input()
    #print('---', s)
    if not s == '.'*w:
        A.append([j for j in s])
if len(A) > 1:
    for j in range(len(A[0])-1,-1,-1):
        
        c = 0
        for i in range(len(A)-1,-1,-1):
            #print(i,j)
            if A[i][j] == '.':
                #print(A[i])
                c +=1
        if c == len(A):
            for k in range(len(A)-1,-1,-1):
                A[k].pop(j)
else:
    for l in range(len(A[0])-1,-1,-1):

        if A[0][l] == '.':
            A[0].pop(l)

for i in range(len(A)):
    print(''.join(A[i]))

Measured memory_bytes: 3188
# 動的計画法で解く
n = int(input())
loc = []
for _ in range(2):
    tmp = list(map(int, input().split()))
    loc.append(tmp)
d = []
for _ in range(2):
    zeros = [0] * n
    d.append(zeros)
# 最終地点からスタート    
d[1][n-1]=loc[1][n-1]
d[0][n-1]=d[1][n-1] + loc[0][n-1]

for i in range(n-1): # 段を入力
    j = (n-2) - i 
    d[1][j] = d[1][j+1] + loc[1][j]
    d[0][j] = max(d[1][j], d[0][j+1]) + loc[0][j]
print(d[0][0])

Measured memory_bytes: 3064
// ABC177B - Substring

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long int ull;
typedef long long int ll;

int main() {
	string S, T;
	cin >> S >> T;

	int ans = 10000;
	int temp;

	for (int i = 0; i < S.size() - T.size() + 1; i++) {
		temp = 0;
		for (int j = 0; j < T.size(); j++) {
			if (S[i+j] != T[j]) {
				temp++;
			}
		}
		ans = min(ans, temp);
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 3564
using System;
using System.Linq;

namespace C
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] NK = Console.ReadLine().Split().Select(i => Convert.ToInt32(i)).ToArray();
            int N = NK[0];
            int K = NK[1];
            int[] A = Console.ReadLine().Split().Select(i => Convert.ToInt32(i)).ToArray();
            int ans = 1;
            N -= K;
            ans += (N % (K - 1) == 0) ? N / (K - 1) : N / (K - 1) + 1;
            Console.WriteLine(ans);
        }
    }
}


Measured memory_bytes: 20192
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pint;

signed main()
{
   int N; cin>>N;
   for(int k=2;k*(k-1)/2<=N;k++){
      if(k*(k-1)/2==N){
         cout<<"Yes"<<endl;
         cout<<k<<endl;
         map<pair<int,int>,int> mp;
         int id=0;
         for(int i=0;i<k;i++){
            for(int j=i+1;j<k;j++){
               id++;
               mp[pint(i,j)]=mp[pint(j,i)]=id;
            }
         }
         for(int i=0;i<k;i++){
            cout<<k-1;
            for(int j=0;j<k;j++){
               if(i==j) continue;
               cout<<' '<<mp[pint(i,j)];
            }
            cout<<endl;
         }
         return 0;
      }
   }
   cout<<"No"<<endl;
   return 0;
}


Measured memory_bytes: 13824
#include "bits/stdc++.h"
using namespace std;
typedef long long li;

li n;
vector<vector<li>> graph;
vector<li> colors;

void dfs(li pos, li parent) {
    for (li next : graph[pos]) {
        if (parent == next) {
            continue;
        }
        li next_color = 1 - colors[pos];
        colors[next] = next_color;
        dfs(next, pos);
    }
}

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

    cin >> n;
    graph = vector<vector<li>>(n);
    colors = vector<li>(n, -1);
    for (int i = 0; i < n - 1; ++i) {
        li a, b;
        cin >> a >> b;
        a--; b--;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    colors[0] = 0;
    dfs(0, -1);

    vector<li> col_counts(2);
    for (int i = 0; i < n; ++i) {
        col_counts[colors[i]]++;
    }
    auto p = min_element(col_counts.begin(), col_counts.end());
    li min_color = p - col_counts.begin();
    li min_count = *p;

    li two_count = (n + 1) / 3;
    vector<li> ans(n);
    if (min_count >= two_count) {
        cerr << 1 << endl;
        li one = 1, two = 2, three = 3;
        for (int i = 0; i < n; ++i) {
            li next;
            if (colors[i] == min_color) {
                next = two;
                two += 3;
            } else {
                next = one;
                one += 3;
            }
            if (next <= n) {
                ans[i] = next;
            } else {
                ans[i] = three;
                three += 3;
            }
        }
    } else {
        // always min_count <= three_count
        cerr << 2 << endl;
        vector<li> ot, th;
        for (int i = 1; i <= n; ++i) {
            if (i % 3 == 0) {
                th.push_back(i);
            } else {
                ot.push_back(i);
            }
        }
        li otp = 0, thp = 0;
        for (int i = 0; i < n; ++i) {
            if (colors[i] != min_color) {
                if (otp < ot.size()) {
                    ans[i] = ot[otp++];
                } else {
                    ans[i] = th[thp++];
                }
            } else {
                ans[i] = th[thp++];
            }
        }
    }

    for (int j = 0; j < n; ++j) {
        cout << ans[j];
        if (j + 1 < n) {
            cout << " ";
        } else {
            cout << endl;
        }
    }
    return 0;
}

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

int main(){
    int W, H, x, y, r;
    cin >> W >> H >> x >> y >> r;

    if ((x-r)<0 || (y-r)<0) {
        cout << "No" << endl;
    }
    else if ((x+r) > W || (y+r) > H){
        cout << "No" << endl;
    }

    else cout << "Yes" << endl;

    return 0;
}


Measured memory_bytes: 3104
//#include <bits/stdc++.h>
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
//#include "boost/multiprecision/cpp_int.hpp"
//typedef boost::multiprecision::cpp_int ll;
typedef long double dd;
#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
typedef pair<dd,dd> d_d;
ll inf=(ll)1E16;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define fi first
#define se second
#define endl "\n"
///////////////////////////


int main(){fastio
    ll n;cin>>n;
    string s;cin>>s;
    ll c=0;
    ll ans=1;
    rep(i,0,2*n-1){
        if((s[i]=='W')^(c%2==0)){
            c++;
        }else{
            ans=mod(ans*c);
            c--;
        }
        if(c<0){
            cout<<0<<endl;return 0;
        }
        //cout<<c<<" ";
    }
    if(c!=0){cout<<0;return 0;}
    rep(i,1,n)ans=mod(ans*i);
    cout<<ans<<endl;
    
    return 0;
}


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

int main(){
    long long int x;
    cin >> x;
    long long int money = 100;
    int ans = 0;
    while(money < x){
        money += money / 100;
        ans++;
    }

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

Measured memory_bytes: 3620
def examA():
    S = SI()
    if S[2]==S[3] and S[4]==S[5]:
        print("Yes")
    else:
        print("No")
    return

def examB():
    X = I()
    ans = 0
    ans += (X//500) * 1000
    X %= 500
    ans += (X//5) * 5
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examB()

"""

"""

Measured memory_bytes: 4848
#include<stdio.h>

int main(void){
    int a[3],i,j,tmp;
    
    for(i=0;i<3;i++){
        scanf("%d",&a[i]);
    }
    
    for(i=0;i<2;i++){
        for(j=2;j>i;j--){
            if(a[j]<a[j-1]){
                tmp=a[j-1];
                a[j-1]=a[j];
                a[j]=tmp;
            }
        }
    }
    for(i=0;i<3;i++){
        if(i==2){
            printf("%d\n",a[i]);
        }else{
            printf("%d ",a[i]);
        }
    }
    return 0;
    
}


Measured memory_bytes: 2100
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

int main()
{
	int n, count = 0, ans = 0;
	cin >> n;
	for (int i = 1; i <= n; i += 2) {
		for (int j = 1; j <= i; j++) {
			if (i % j == 0) {
				count++;
			}
		}
		if (count == 8) {
			ans++;
		}
		count = 0;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3192
#!/usr/bin/env python3
from itertools import product
n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]

m = 0
xy.sort(key=lambda x: (x[0], x[1]))
for l in range(n - 1):
    for r in range(l + 1, n):
        p = xy[r][0] - xy[l][0]
        q = xy[r][1] - xy[l][1]
        c = 0
        for i in range(n - 1):
            for j in range(i + 1, n):
                if xy[j][0] - xy[i][0] != p: continue
                if xy[j][1] - xy[i][1] != q: continue
                c += 1
                break
        m = max(m, c)

xy.sort(key=lambda x: (x[1], x[0]))
for l in range(n - 1):
    for r in range(l + 1, n):
        p = xy[r][0] - xy[l][0]
        q = xy[r][1] - xy[l][1]
        c = 0
        for i in range(n - 1):
            for j in range(i + 1, n):
                if xy[j][0] - xy[i][0] != p: continue
                if xy[j][1] - xy[i][1] != q: continue
                c += 1
                break
        m = max(m, c)

print(n - m)


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

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


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

int main(){
  int n; cin >>n;
  vector<int>a(n);
  for(int i=0; i<n; i++) cin >>a[i];
  sort(a.begin(),a.end());
  for(int i=0; i<n-1; i++)
  {if(a[i]==a[i+1]){cout <<"NO"; return 0;}}
  cout <<"YES";
return 0;}

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

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

    long long ans = 0;
    if(n%2 == 0){
        for(long long i=5;i<=n;i*=5){
            ans += n/(i*2);
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
n = int(input())
A = list(map(int, input().split()))
count = 1
direction = 0
for a, b in zip(A, A[1:]):
	dif = b - a
	if direction == 0:
		if dif > 0:
			direction = 1
		elif dif < 0:
			direction = -1
	elif (direction == 1 and dif < 0) or (direction == -1 and dif > 0):
		count += 1
		direction = 0
print(count)

Measured memory_bytes: 62704
<?php
while ($line = fgets(STDIN)) {
   $tmp[] = trim($line);
}
foreach ($tmp as $key => $value) {
  $array[] = explode(" ", $value);
}
$ans = 0;
$n = $array[0][0];
$d = $array[0][1];
for($i = 1; $i <= $n; $i++){
    if(sqrt((pow($array[$i][0], 2) + pow($array[$i][1], 2))) <= $d){
        $ans++;
    }
}
echo $ans;

?>

Measured memory_bytes: 122424
s = input()
t = input()

S = []
T = []
for i in s:
    S.append(i)
S.sort()
for i in t:
    T.append(i)
    T.sort(reverse = True)

Sstring = "".join(S)
Tstring = "".join(T)
print("Yes" if Sstring < Tstring else "No")
   

Measured memory_bytes: 3060
#![allow(non_snake_case)]

use std::io::{stdin, Read};
use std::str::FromStr;
fn read_option<T: FromStr>() -> Option<T> {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok()
}
fn read<T: FromStr>() -> T {
    let opt = read_option();
    opt.expect("failed to parse token")
}

fn main() {
    let H: usize = read();
    let W: usize = read();
    let D: usize = read();
    let mut board: Vec<Vec<usize>> = vec![];
    for _ in 0..H {
        let mut vec: Vec<usize> = vec![];
        for _ in 0..W {
            let v = read::<usize>() - 1;
            vec.push(v);
        }
        board.push(vec);
    }
    let Q: usize = read();
    let queries: Vec<(usize, usize)> = (0..Q)
        .map(|_| (read::<usize>() - 1, read::<usize>() - 1))
        .collect();
    let ans = solve(D, &board, &queries);
    println!(
        "{}",
        ans.iter()
            .map(|i| i.to_string())
            .collect::<Vec<_>>()
            .join("\n")
    );
}

fn solve(d: usize, board: &[Vec<usize>], queries: &[(usize, usize)]) -> Vec<usize> {
    let mut rev_board: Vec<(usize, usize)> = vec![(0, 0); board.len() * board[0].len()];
    for (i, row) in board.iter().enumerate() {
        for (j, &v) in row.iter().enumerate() {
            rev_board[v] = (i, j);
        }
    }
    let mut scores = vec![vec![0]; d];
    for i in d..rev_board.len() {
        let rem = i % d;
        let before = rev_board[i - d];
        let now = rev_board[i];
        let score = (before.0 as isize - now.0 as isize).abs() as usize
            + (before.1 as isize - now.1 as isize).abs() as usize;
        let last = scores[rem].last().unwrap().clone();
        scores[rem].push(score + last);
    }
    queries
        .iter()
        .map(|&(start, end)| {
            let rem = start % d;
            scores[rem][end / d] - scores[rem][start / d]
        })
        .collect()
}


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

using namespace std;

#define FOR(i, n) for(int i = 0; i < (int) n; i++)
#define PB push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define F first
#define S second

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;

const int MOD = 998244353;

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

	int n; cin >> n;
	int ans = 0;
	FOR(i, n){
		int x; cin >> x;
		if(i%2 == 0 && x%2){
			ans ++;
		}
	}

	cout << ans << '\n';

	return 0;
}


Measured memory_bytes: 3636
n = int(input())
h = [int(x) for x in input().split()]
dp = [0] * n
for i in range(n):
    if i == 0:
        continue
    if i == 1:
        dp[i] = dp[i - 1] + abs(h[i] - h[i - 1])
    if i >= 2:
        dp[i] = min(dp[i - 1] + abs(h[i] - h[i - 1]), dp[i - 2] + abs(h[i] - h[i - 2]))
print(dp[n - 1])

Measured memory_bytes: 13928
from sys import stdin
import math


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, X, T = list(map(int, _in[0].split(' ')))  # type:list(int)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    ans = math.ceil(N / X) * T
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 61844
// Best practice

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file 
#include <ext/pb_ds/tree_policy.hpp> 
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <functional> // for less 

#define int         long long
#define pb          emplace_back
#define pf          emplace_front
#define all(a)      (a).begin(),(a).end()
#define rall(a)     (a).rbegin(),(a).rend()
#define x           first
#define y           second
#define endl        '\n'
#define tezz        ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
using namespace __gnu_pbds; 
 
typedef tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update> pbds; 

#define fbo find_by_order
#define ook order_of_key

signed main() {
   tezz
   
   string s;
   cin >> s;
   if(s[0]==s[1] && s[2]==s[1])cout << "No" << endl;
   else cout << "Yes" << endl;
  
   return 0;
}




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

using namespace std;

typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<bool> vb;
typedef pair<ll,ll> pll;
typedef vector<pll> vpll;


const ll mod=1e9+7;
const ll inf=1e16; 

#define rep(i,m,n) for(ll i=m;i<n;i++)
#define repr(i,m,n) for(ll i=m;i>=n;i--)


struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= 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 { return mint(*this) /= a;}
};
istream& operator>>(istream& is, mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}
 


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

 ll n;
  cin >> n;
 vll c(n);
  rep(i,0,n) cin >> c[i]; 
  sort(c.begin(),c.end());
  
  
  mint res=0;
 vector<mint> two(n+1);
  two[0]=1;
  rep(i,0,n) two[i+1]=two[i]*2;
  
  rep(i,0,n){
    ll l=i,r=n-1-i;
    mint now=two[r];
    if(r!=0) now+=two[r-1]*r;
    now*=two[l];
    now*=c[i];
    res+=now;
  }

   res*=two[n];
  
  cout << res.x << endl;
  
}


Measured memory_bytes: 6316
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cassert>
#include <iostream>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <sstream>
#include <bitset>

using namespace std;
typedef long long ll;

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


    ll ans=0;
    ll anss =0;
    ll count=0;
    ll i,j;
    ll aa[5];
    ll k;
    vector<ll> d;

    ll Q,N;
    string S;
    cin>>Q>>N;
    if(Q==N){
        ans=2*Q;
    }else{
        ans=max(Q,N)*2-1;
    }
    

        cout<< ans << endl;

 
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	string s1,s2;	
	int len,i;
	cin>>s1;
	len=s1.size();
	for(i=len-1;i>=0;i--)
	{
		switch(s1[i])
		{
			case 'b':s2+='d';break;
			case 'd':s2+='b';break;
			case 'q':s2+='p';break;
			case 'p':s2+='q';break;
			default: s2+=s1[i];
		}
	}
//	cout<<s1<<endl<<s2;	
	if(s1==s2) cout<<"Yes\n";
	else cout<<"No\n";
	return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 100;
int h[N];
int dp[N];

int main() {
  int n, k;
  cin >> n >> k;
  for (int i = 0; i < n; i++) cin >> h[i];
  dp[n - 1] = 0;
  dp[n - 2] = abs(h[n - 1] - h[n - 2]);

  for (int i = n - 3; i >= 0; i--) {
    int minV = 1e9;
    int l = min(k, n - i - 1);
    for (int j = 1; j <= l; j++) {
      minV = min(minV, dp[i + j] + abs(h[i] - h[i + j]));
    }
    dp[i] = minV;
  }
  cout << dp[0];
  return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define N 2010
int n;
int ai[N];
vector <int> bi[N], bf[N];
int vis[N];
int in[N];
struct comp
{
    int operator() (int a, int b) {return ai[a] < ai[b];}
};
priority_queue <int, vector <int>, comp> H;
void dfs(int t)
{
    vis[t] = 1;
    for (int i = 0; i < bi[t].size(); ++ i)
        if (!vis[bi[t][i]])
        {
            bf[t].push_back(bi[t][i]);
            in[bi[t][i]] ++;
            dfs(bi[t][i]);
        }
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++ i)
        cin >> ai[i];
    sort(ai + 1, ai + n + 1);
    for (int i = 1; i <= n; ++ i)
        for (int j = i + 1; j <= n; ++ j)
            if (__gcd(ai[i], ai[j]) != 1)
                bi[i].push_back(j),
                bi[j].push_back(i);

    for (int i = 1; i <= n; ++ i)
        if (!vis[i]) dfs(i);

    for (int i = 1; i <= n; ++ i)
        if (!in[i]) H.push(i);
    while (!H.empty())
    {
        int hd = H.top(); H.pop();
        cout << ai[hd] << " ";
        for (int i = 0; i < bf[hd].size(); ++ i)
        {
            in[bf[hd][i]] --;
            if (!in[bf[hd][i]]) H.push(bf[hd][i]);
        }
    }
}


Measured memory_bytes: 17792
n,m=map(int,input().split())
e=[[]for _ in range(n)]
for _ in range(m):
  a,b=map(int,input().split())
  e[a-1]+=[b-1]
  e[b-1]+=[a-1]
def dfs(now,vis):
  vis+=[now]
  if len(vis)==n:return 1
  res=0
  for to in e[now]:
    if to not in vis:
      res+=dfs(to,vis[:])
  return res
print(dfs(0,[]))

Measured memory_bytes: 73608
#include<iostream>
using namespace std;
const int INF = (1<<21);
int G[101][101];
int c,n,m,s,d;

int dij(){
  int D[101][11];
  bool V[101][11];
  for(int i=0;i<n;i++){
    for(int j=0;j<c+1;j++){
      D[i][j]=INF;
      V[i][j]=false;
    }
  }
  D[s][c]=0;
  while(1){
    int minv=INF,u,w;
    for(int i=0;i<n;i++){
      for(int j=0;j<c+1;j++){
	if(!V[i][j] && minv>D[i][j]){
	  minv=D[i][j];
	  u=i;
	  w=j;
	}
      }
    }
    
    V[u][w]=true;
    if(minv == INF) break;
    for(int i=0;i<n;i++){
      if(G[u][i] == INF) continue;
      D[i][w]=min(D[i][w],D[u][w]+G[u][i]);
      if( w ){
	D[i][w-1]=min(D[i][w-1],D[u][w]+G[u][i]/2);
      }
    }
  }

  int minv=INF;
  for(int i=0;i<c+1;i++){
    if(D[d][i]<minv){
      minv=D[d][i];
    }
  }

  return minv;  
}

int main(){
  
  while(cin>> c>> n>> m>> s>> d && c){
    d--;
    s--;
    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
	G[i][j]=INF;
      }
    }
    
    for(int i=0;i<m;i++){
      int a,b,f;
      cin>> a>> b>> f;
      a--;
      b--;
      G[a][b]=G[b][a]=f;
    }
    
    cout<< dij()<< endl;
  }
}

Measured memory_bytes: 1204
#include <stdio.h>
int main(void)
{
    long long int n,a,b,i,ans=0;
    scanf("%lld%lld%lld", &n, &a, &b);
    long long int x[n];
    for(i=0; i<n; i++) scanf("%lld", &x[i]);
    for(i=0; i<n-1; i++)
    {
        if((x[i+1]-x[i])*a>b) ans+=b;
        else ans+=(x[i+1]-x[i])*a;
    }
    printf("%lld", ans);
    return 0;
}

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

#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define all(v) v.begin(), v.end()
#define ar array

#define F first
#define S second
#define sz(x) int(x.size())
using namespace std;
using ll = long long;
using pii = pair <int, int>;
using pll = pair <ll, ll>;
using ld = long double;

// const int mod = 1e9 + 7;
const int mod = 998244353;
const ll inf = 2e9;
const ll INF = 1e18;
const ld EPS = 1e-7;

const int N = 1e6 + 5;

vector <int> add[N];

void solve () {
	int n, m;
	cin >> n >> m;
	for (int i = 1, a, b ; i <= n ; ++ i) {
		cin >> a >> b;
		add[a].push_back (b);
	}
	multiset <int> s;
	ll best = 0;
	for (int i = 1 ; i <= m ; ++ i) {
		for (int j : add[i]) s.insert (j);
		if (s.size()) {
			int x = *s.rbegin();
			s.erase (s.find (x));
			best += x;
		}
	}
	cout << best;
}

int main () {
	ios;
	int tt = 1;
	// cin >> tt;
	while (tt--) {
		solve();
		cout << "\n";
	}
}




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

#define rep(i, j) for (int i = 0; i < j; i++)
#define all(obj) (obj).begin(), (obj).end()
#define rall(obj) (obj).rbegin(), (obj).rend()
typedef long long int ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<pii> vpii;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n;
    cin >> n;

    if (n % 2 == 0) n--;

    cout << n / 2 << endl;

    return 0;
}


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

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

    vector<int> A(N);
    rep(i, N) cin >> A.at(i);

    unsigned long long steps = 0;
    rep(i, N - 1) {
        if(A.at(i) > A.at(i + 1)) {
            steps += A.at(i) - A.at(i + 1);
            A.at(i + 1) = A.at(i);
        }
    }
    cout << steps << endl;
}


Measured memory_bytes: 3976
N = int(input())
l = []
l.append(input())
ans = 'Yes'

for i in range(1, N):
  t = input()
  if t in l:
    ans = 'No'
    break
  elif l[i-1][-1] ==  t[0]:
    l.append(t)
  else:
    ans = 'No'
    break
print(ans)

Measured memory_bytes: 8932
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define rep(i, n) for (ll i = 0; i < n; i++)
#define rrep(i, n) for (ll i = n - 1; i >= 0; i--)
#define Rep(i, r, n) for (ll i = r; i < n; i++)
#define RRep(i, r, n) for (ll i = n - 1; i <= r; i--)
#define debug(x) cout << #x << ' ' << '=' << ' ' << (x) << endl;
#define fs first
#define sc second
#define int long long
#define pb push_back
#define mp make_pair
const int dx[] = {0, -1, 0, 1};
const int dy[] = {1, 0, -1, 0};
const int MOD = (1000000007);
//const int MOD = (998244353);
//const int INF = (1 << 30)-1;
const int INF = (1LL << 60)-1;
const double EPS = (1 >> 30);

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return 1;} return 0;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return 1;} return 0;}

using Graph = vector<vector<pair<int, int>>>;
using Ki = vector<vector<int>>;
using Vi = vector<int>;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(10);
    //---------------------------------------------
    
    int n;
    cin>>n;
    vector<string> s(3);
    rep(i,3){
        cin>>s[i];
    }
    ll ans=0;
    rep(i,n){
        ll memo=0;
        if(s[0][i]!=s[1][i]) memo++;
        if(s[0][i]!=s[2][i]) memo++;
        if(s[2][i]!=s[1][i]) memo++;
        ans+=max((ll)0,memo-1);
    }
    cout<<ans<<endl;

}

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

int SCmp(string S1, string S2) {
	if (S1 == S2) return 0;
	for (int i = 0; i < min(S1.size(), S2.size()); i++) {
		if (S1[i] < S2[i]) return 1;
		if (S1[i] > S2[i]) return -1;
	}
	if (S1.size() < S2.size()) return 1;
	else return -1;
}

int main() {
	int N;
	string S[10000] = {}, T = {};
	int first = 1, end = 1;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> S[i];
	}
	cin >> T;
	for (int i = 0; i < N; i++) {
		string S1 = S[i], S2 = S[i];
		for (int j = 0; j < S[i].size(); j++) {
			if (S[i][j] == '?') S1[j] = 'a', S2[j] = 'z';
		}
		if (SCmp(S1, T) >= 0) end++;
		if (SCmp(S2, T) > 0) first++;
	}
	for (int i = first; i < end; i++) {
		cout << i << " ";
	}
	cout << end << endl;
}

Measured memory_bytes: 1024