akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pb push_back
typedef long long int ll;
const int N=2e5+5;
int n,k,c,tmp,pre[N],suf[N];
string s;
int main(){
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin>>n>>k>>c>>s;
    tmp=k;
    for(int i=0;i<n&&tmp;i++){
        if(s[i]=='o'){
            tmp--;
            pre[i]=k-tmp;
            i+=c;
        }
    }
    if(tmp){
        for(int i=0;i<n;i++)
            pre[i]=(s[i]=='o');
    }
    tmp=k;
    for(int i=n-1;i>=0&&tmp;i--){
        if(s[i]=='o'){
            if(pre[i]<= tmp) suf[i]=1;
            tmp--;
            i-=c;
        }
    }
    if(tmp){
        for(int i=0;i<n;i++)
            suf[i]=(s[i]=='o');
    }
    for(int i=0;i<n;i++){
        if(pre[i]&&suf[i])
            cout<<i+1<<'\n';
    }
    return 0;
}


Measured memory_bytes: 3348
#include <iostream>
#include <string>
#include <cctype>

using namespace std;

int main() {
  int a = 0, z = 0;
  string S;
  cin >> S;

  a = S.find('A');
  z = S.rfind('Z');

  cout << (z - a) + 1 << endl;
  return 0;
}


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


int N, M;
int edge[50][50];
bool visited[10];

int search(int curr, int step) {
    if (step == N) {
        return 1;
    }
    int pattern = 0;
    visited[curr] = true;
    rep(i, N) {
        if (edge[curr][i] > 0 && !visited[i]) {
            pattern += search(i, step + 1);
        }
    }
    visited[curr] = false;
    return pattern;
}

int main(){
    cin >> N >> M;
    rep(i, M) {
        int a, b;
        cin >> a >> b;
        a--;b--;
        edge[a][b] = 1;
        edge[b][a] = 1;
    }
    int count = search(0, 1);
    cout << count << endl;
    return 0;
}

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

    int n,d;
    cin>>n;
    int c=0;
    while(n>0){
        d=n%10;
        if(d==7){
            c++;
            break;
        }
        n=n/10;
    }
    if(c==0){
        cout<<"No"<<endl;
    }
    else{
        cout<<"Yes"<<endl;
    }


}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
// using namespace atcoder;
typedef long long ll;
/* clang-format off */
#define MOD 1000000007
#define INF 1000000000000000000ll
#define REP(i, n) for (ll i = 0, i##_len = (n); i < i##_len; ++i)
#define ALL(a) (a).begin(), (a).end()
//#define __DEBUG__
#ifdef __DEBUG__
#define CH_P(a) cout <<"check_point("<<#a<<")" << "\n";
#define DEBUG(x) cout<<#x<<":"<<x<<"\n"
#define DEBUGS(v) cout << #v << ":";for(auto x:v){cout<<x<<" ";}cout<<"\n"
#endif
#ifndef __DEBUG__
#define CH_P(a) 
#define DEBUG(x) 
#define DEBUGS(v) 
#endif
/* clang-format on */

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll n, m;
  cin >> n >> m;
  vector<ll> a(n), b(m), c(m);
  vector<pair<ll, ll>> d(m);
  REP(i, n) cin >> a[i];
  REP(i, m) {
    cin >> b[i] >> c[i];
    d[i] = {c[i], b[i]};
  }
  sort(ALL(a));
  sort(ALL(d));
  reverse(ALL(d));
  queue<ll> q;
  ll tmp = 0;
  REP(i, m) {
    tmp += d[i].second;
    REP(j, d[i].second) q.push(d[i].first);
    if (tmp > n) break;
  }
  REP(i, n) {
    if (q.empty()) break;
    ll t = q.front();
    q.pop();
    if (a[i] < t)
      a[i] = t;
    else
      break;
  }
  ll ans = 0;
  REP(i, n) { ans += a[i]; }
  cout << ans << '\n';
  DEBUGS(a);
  return 0;
}


Measured memory_bytes: 8708
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <sstream>
#include <set>
#include <map>
#include <iostream>
#include <utility>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <limits.h>
#include <cstring>
#include <tuple>
#include <cassert>
#include <numeric>
using namespace std;
// type alias
typedef long long LL;
typedef vector < int > VI;
typedef unordered_map < int, int > MAPII;
typedef unordered_set < int > SETI;
typedef pair< int , int > II;
typedef tuple< int, int, int > III;
// repetition
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)
#define REPE(i,n)  for(int i=0;i<=(n);++i)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  for(int i=0;i<(n);++i)
#define FORR(x,arr) for(auto& x:arr)
#define SZ(a) int((a).size())
// DP
#define MINUS(dp) memset(dp, -1, sizeof(dp))
#define ZERO(dp) memset(dp, 0, sizeof(dp))
// minmax
#define SMAX(a,b) a = max(a,b)
#define SMIN(a,b) a = min(a,b)
// debug cerr
#define TRACE true
#define dump(x) if(TRACE) { cerr << #x << " = " << (x) << endl; }
#define dump2(x,y) if(TRACE) { cerr << #x << " = " << (x) << ", " << #y << " = " << (y) << endl; }
#define dump3(x,y,z) if(TRACE) { cerr << #x << " = " << (x) << ", " << #y << " = " << (y) << ", " << #z << " = " << (z) << endl; }
#define dump4(x,y,z,a) if(TRACE) { cerr << #x << " = " << (x) << ", " << #y << " = " << (y) << ", " << #z << " = " << (z) << ", " << #a << " = " << (a) << endl; }
#define dumpAR(ar) if(TRACE) { FORR(x,(ar)) { cerr << x << ','; } cerr << endl; }

LL solve(int A, int B, int C, int X, int Y) {
  LL res=1e10;
  REPE(c,2*max(X,Y)) {
    LL a=max(0,X-c/2);
    LL b=max(0,Y-c/2);
    SMIN(res,a*A+b*B+c*C);
  }
  return res;
}

int main() {
  int A,B,C,X,Y;
  cin >> A >> B >> C >> X >> Y;
  cout << solve(A,B,C,X,Y) << endl;
  return 0;
}


Measured memory_bytes: 256
s=input()
while True:
    if len(s)==0:
        print("YES")
        break
    elif s[:7]=="dreamer":
        if s[7:11]=="aser":
            s=s[11:]
        elif s[7:10]=="ase":
            s=s[10:]
        #順番に注意
        else:
            s=s[7:]
    elif s[:6]=="eraser":
        s=s[6:]
    elif s[:5]=="dream" or s[:5]=="erase":
        s=s[5:]
    else:
        print("NO")
        break


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

const ll MAXN = 200000;

ll A, B, tmp=0;
vector<ll> ans;

ll euclidean_gcd(ll a, ll b) {
    if(a < b) return euclidean_gcd(b, a);
    ll r;
    while ((r=a%b)) {
        a = b;
        b = r;
    }
    return b;
}

void soinsuu(ll num){
    for(int i=2;i*i<=num;i++) {
        ll flag=0;
        while(num%i==0) {
            num/=i;
            if(flag==0) ans.push_back(i);
            flag = 1;
        }
    }
    if(num!=1) ans.push_back(num);
}

signed main(){
    cin >> A >> B;
    ans.push_back(1);
    soinsuu(euclidean_gcd(A, B));
    cout << ans.size() << endl;
    return 0;
}

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

int main() {
  int N, k, num = 1; cin >> N >> k;
  for (int i = 0; i < N; i++) {
    if (num * 2 > num + k) {
      num += k;
    }
    else {
      num *= 2;
    }
  }
  cout << num << endl;
}



Measured memory_bytes: 256
#include<iostream>
#include<bits/stdc++.h>
#include<string>
using namespace std;
int main()
{
  int n, T ;
  cin >> n >> T  ;
  
  int min =1001 ;
  
  for(int i=0; i<n; i++){
    int c, t;
    cin >> c >> t;
    if(t <= T && c < min){
      min = c;
    }
  }

  if(min == 1001)
    cout << "TLE" << endl ;
  else 
    cout << min << endl ;
  
    return 0 ;    
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n;
long long a[100100];
int main(){
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	long long res=0;
	for(int i=1;i<=n;i++){
		res+=a[i]/2;
		a[i]%=2;
		if(a[i]&&a[i+1])
		{
			res++;
			a[i]=0;
			a[i+1]--;
		}
	}
	cout<<res<<endl;
	return 0;
}


Measured memory_bytes: 1024
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

N=int(input())
div=make_divisors(N)

from math import sqrt

tmpmin=10**16
for i in range(len(div)):
  if tmpmin>abs(sqrt(N)-div[i]):
    tmpmin=abs(sqrt(N)-div[i])
    minidx=i

a=div[minidx]
b=N//a

print(a-1+b-1)

Measured memory_bytes: 3372
#include <bits/stdc++.h>
using namespace std;
 
int main() 
{
  int A, B;
  int total;
  int numA;
  cin >> A >> B;
  
  if (B == 1) {
    cout << 0 << endl;
  }
  else {
  	for (total = A, numA = 1; total < B; total+=A-1, numA++)
    	;
  	cout << numA << endl;
  }
  return 0;  
}

Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
#include<iomanip>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
#include<string>
#include<math.h>
using namespace std;

int main(){
    int H,W,h,w;
    cin >> H >> W >> h >> w;
    cout << H * W - (H * w + W * h- (h * w));
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<utility>
#include<algorithm>

using namespace std;

int main(){
    int n;
    scanf("%d", &n);

    int a[100];
    for(int i = 0; i < n; i++){
        scanf("%d",&a[i]);
    }

    int cnt = 0;

    for(int i = 0; i < n; i++){
        int minj = i;
        for(int j = i; j < n; j++){
            if(a[minj] > a[j]){
                minj = j;
            }
        }
        if(a[i] != a[minj]){
            swap(a[i], a[minj]);
            cnt++;
        }
    }

    for(int i = 0; i < n-1; i++){
        printf("%d ", a[i]);
    }
    printf("%d\n", a[n-1]);
    printf("%d\n", cnt);
}



Measured memory_bytes: 2732
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const string ln = "\n";
constexpr int INF = 1001001001;
constexpr int MOD = 1000000007;

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

  int n;
  cin >> n;
  vector<int> x(n);
  for (int i = 0; i < n; i++) {
    cin >> x[i];
  }

  ll ans = INF;
  for (int p = 1; p <= 100; p++) {
    ll sum = 0;
    for (int i = 0; i < n; i++) {
      ll t = (x[i] - p);
      sum += t * t;
    }
    if (sum < ans) {
      ans = sum;
    }
  }

  cout << ans << ln;

  return 0;
}

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

using namespace std;

int main()
{
  int N;
  int A,B,C,K;
  int count=0;
  cin>>A>>B>>C>>K;
  for(int i=0;i<=K;i++){
    if(B>A&&C>B){
      cout<<"Yes";
      return 0;
    }else if(B<=A){
      B=2*B;
    }else if(C<=B){
      C=2*C;
    }
  }
  cout<<"No";
  return 0;
}





Measured memory_bytes: 3632
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int mod = (int)1e9+7;
const int nax = 101;
int a[nax];
int n;
vector<ll> dp;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int k;
	cin>>n>>k;
	vector<ll> _dp(k+1,1);
	dp = _dp;
	auto pref = [&](int i, int j){
		if(i>0) 
			return (mod + dp[j]-dp[i-1])%mod;
		else return dp[j];
	};
	ll ans = 0;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		vector<ll> new_dp(k+1);
		for(int j=0;j<=k;j++){
			new_dp[j] = pref(j-x,j);
		}
		dp = new_dp;
		ans = new_dp[k];
		ll sum = 0;
		for(int j=0;j<=k;j++){
			sum = (sum + dp[j])%mod;
			dp[j] = sum;
		}
	}
	cout<<ans;
    return 0;
}









Measured memory_bytes: 2672
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <vector>
using namespace std;
typedef long long ll;
ll const INF = 1LL << 60;

vector<bool> sieve(int N) {
  vector<bool> is_prime(N + 1);
  for (int i = 0; i < N + 1; i++) {
    is_prime[i] = true;
  }
  is_prime[0] = false;
  is_prime[1] = false;
  for (int i = 2; i * i <= N; ++i) {
    if (is_prime[i]) {
      for (int j = 2; i * j <= N; ++j) is_prime[i * j] = false;
    }
  }
  return is_prime;
}

int main() {
  ll Q;
  cin >> Q;
  int l, r, max_num = 0;
  vector<pair<ll, ll>> query;
  for (int i = 0; i < Q; i++) {
    cin >> l >> r;
    max_num = max(max_num, r);
    query.push_back({l, r});
  }
  vector<bool> is_prime = sieve(max_num);
  vector<ll> prime_cnt(max_num + 1, 0);
  for (int i = 2; i < is_prime.size(); i++) {
    if (is_prime[i] && is_prime[(i + 1) / 2]) prime_cnt[i]++;
    prime_cnt[i] += prime_cnt[i - 1];
  }
  for (auto q : query) {
    l = q.first;
    r = q.second;
    ll cnt = prime_cnt[r] - prime_cnt[l - 1];
    cout << cnt << endl;
  }
  return 0;
}

Measured memory_bytes: 3056
import java.util.Scanner;

public class Main{
	public static void main(String args[]){

	Scanner scan = new Scanner(System.in);
	
	int sc = scan.nextInt();
	int h = sc/3600;
	int m = (sc%3600)/60;
	int s = sc%60;

	System.out.printf("%d:%d:%d\n",h,m,s);
	}
}


Measured memory_bytes: 26508
import sys


def input():
    return sys.stdin.readline()[:-1]

# N = int(input())
# A = [int(x) for x in input().split()]
# a, b, c = map(int, input().split())
# name1 = str(input())
# alph = {"A": 1, "B": 2, "C": 3, "D": 4, "E": 5}


a,b=map(int,input().split())
print(a+int(b/2))

Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define repr(i,from,to) for(int (i)=(from);(i)<(to);(i)++)
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
const bool debug=true;
// const bool debug=false;
#define DEBUG if(debug==true)
#define vprint(x) for(auto a:(x)) cout << x << endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MOD = 1000000007;
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) { a = b; return true;}
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) { a = b; return true;}
    return false;
}
int main(void) {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll h,w;cin>>h>>w;
    ll ncol = 26000;
    vector<vector<vector<bool>>> nums(h, vector<vector<bool>>(w, vector<bool>(ncol, false)));
    // vector<vector<set<ll>>> nums(h, vector<set<ll>>(w,set<ll>())); 
    vector<vector<ll>> a(h, vector<ll>(w,0)), b(h, vector<ll>(w,0)), ab(h, vector<ll>(w,0));
    rep(i,h) {
        rep(j,w) {
            cin>>a[i][j];
        }
    }
    rep(i,h) {
        rep(j,w) {
            cin>>b[i][j];
        }
    }
    rep(i,h) {
        rep(j,w) {
            ab[i][j] = a[i][j] - b[i][j];
        }
    }
    // nums[0][0].insert(ab[0][0]);
    ll base = 12810;
    nums[0][0][ab[0][0]+base] = true;
    rep(i,h) {
        rep(j,w) {
            if (i > 0) {
                rep(k, ncol) {
                    if (nums[i-1][j][k]) {
                        nums[i][j][k+ab[i][j]] = true;
                        nums[i][j][k-ab[i][j]] = true;
                    }
                }
            }
            if (j > 0) {
                rep(k, ncol) {
                    if (nums[i][j-1][k]) {
                        nums[i][j][k+ab[i][j]] = true;
                        nums[i][j][k-ab[i][j]] = true;
                    }
                }
            }
        }
    }
    ll res = 10000000;
    rep(i,ncol) {
        if (nums[h-1][w-1][i]) {
            chmin(res, abs(ll(i-base)));
        }
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 22656
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mx 1

int main()
{	
	ios_base::sync_with_stdio(0);
	ll a;
	string str;;
	while(cin>>a>>str){
		ll b = str[0]-'0';
		ll c = (str[2]-'0')*10 + (str[3]-'0');
		ll ans = a*b + (a*c)/100;
		cout<<ans<<endl;
	}
}



Measured memory_bytes: 3664
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		double r = scanner.nextDouble();
		scanner.close();
		
		System.out.print(String.format("%.5f", r * r * Math.PI) + " " + String.format("%.5f", 2 * r * Math.PI));
	}
} 



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

#define int long long
#define ll long long
#define ffor(i,n) for(int i = 0;i < (n); ++i)
#define fro(i,j,n) for(int i = (j);i < (n); ++i)
#define all(v) v.begin(),v.end()
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int,int>
#define vpii vector<pii>
#define ff first
#define ss second
const int mod = 1e9 + 7;
template<typename T>
T add(T a,T b){
	return (a + b)%mod;
}
template<typename T>
T sub(T a,T b){
	return add(a,mod - b);
}
template<typename T>
T mul(T a,T b){
	return (a*b)%mod;
}

int n,k;
const int mxn = 2e5 + 10;
vector<int> adj[mxn];

int len = 0;
vector<int> cycle;
vector<bool> vis;
int cycle_head;
void dfs(int root){
	cycle.push_back(root);
	len++;
	vis[root] = true;
	for(auto x : adj[root]){
		if(vis[x]){
			cycle_head = x;
			return;
		}else{
			dfs(x);
		}
	}
}

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n,k;
	cin >> n >> k;
	vis.resize(n,false);
	ffor(i,n){
		int x;
		cin >> x;
		--x;
		adj[i].push_back(x);
	}
	dfs(0);
	// cout << len;
	vector<int> real_cycle;
	int i = 0;
	int cnt_extra = 0;
	while(cycle[i] != cycle_head && (i < cycle.size())){
		if(k == 0){
			cout << cycle[i] + 1;
			return 0;
		}
		--k;
		++i;
		++cnt_extra;
	}	
	while(i < cycle.size()){	
		real_cycle.push_back(cycle[i]);
		++i;
	}
	k %= (int)real_cycle.size();
	// cout << k;
	cout << real_cycle[k] + 1;
	
}	

Measured memory_bytes: 26008
#include <stdio.h>
int main(void){
    int H, W;
    int i, j;
    while(1){
        scanf("%d""%d", &H, &W);
        if(H==0 && W==0){
            break;
        }
        for(i=0; i<H; i++){
            for(j=0; j<W; j++){
                if( i==0 || i==H-1 || j==0 || j==W-1 ){
                    printf("#");
                }
                else{
                    printf(".");
                }
            }
            printf("\n");
        }
        printf("\n");
    }
}



Measured memory_bytes: 2032
import java.util.* ;
class Main {
  public static void main(String[] args) {
    
    Scanner scan = new Scanner(System.in);
  int a = scan.nextInt();
    int b =scan.nextInt();
    int c = scan.nextInt();
    int d = scan.nextInt();
    
    if(Math.abs(a-c) <= d || (Math.abs(a-b)<= d && Math.abs(b-c)<=d) ){
      System.out.println("Yes");
    }else{
      System.out.println("No");
    }
    
  }
}


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

int main(){
	int n, m, S, max;
	cin>>n>>m;
	S = m;
	max = m;
	for(int i = 1; i <= n; i++){
		int a, b;
		cin>>a>>b;
		S = S + a - b;
		if (S > max) max = S;
		if(S < 0) {
			max = 0;
			break;
		}
		if (S > max) max = S;
	}
	cout<<max<<endl;

	return 0;
}



Measured memory_bytes: 3096
def main():
    n, m = map(int, input().split())
    ab_list = [list(map(int, input().split())) for _ in range(n)]
    ab_list.sort(key=lambda x: x[0])
    ans, cnt = 0, 0

    for i in range(n):
        ans += ab_list[i][0] * ab_list[i][1]
        cnt += ab_list[i][1]
        if cnt > m:
            ans -= ab_list[i][0] * (cnt - m)
            break

    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 90128
from copy import deepcopy

cnt = 0
depth = 0


def main():
    n, m = map(int, input().split())
    adj = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        adj[a].append(b)
        adj[b].append(a)

    def f(u, d):
        global cnt, depth
        cp = deepcopy(d)
        cp[u] = depth
        if cp.count(-1) == 0:
            cnt += 1
        else:
            vs = adj[u]
            depth += 1
            for v in vs:
                if cp[v] == -1:
                    f(v, cp)
            depth -= 1

    f(0, [-1] * n)

    print(cnt)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3444
import java.io.*;
import java.util.*;

class Main {

	public static void main(String[] args) throws Exception {
		final Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		int R = sc.nextInt();
		int[] r = new int[R];
		for (int i = 0; i < R; i++) {
			r[i] = sc.nextInt() - 1;
		}

		long[][] d = new long[N][N];
		for (int i = 0; i < N; i++) {
			Arrays.fill(d[i], 200000002L);
		}

		for (int i = 0; i < M; i++) {
			int a = sc.nextInt() - 1, b = sc.nextInt() - 1;
			int c = sc.nextInt();
			d[a][b] = d[b][a] = c;
		}

		for (int k = 0; k < N; k++) {
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);
				}
			}
		}

		long[][] dp = new long[(1 << R)][N];
		for (int i = 0; i < (1 << R); i++) {
			Arrays.fill(dp[i], 200000002L);
		}

		for (int i = 0; i < R; i++) {
			dp[1 << i][r[i]] = 0;
		}

		for (int i = 0; i < (1 << R); i++) {
			for (int j = 0; j < R; j++) {
				if (((1 << j) & i) > 0) continue;
				for (int k = 0; k < N; k++) {
					dp[i | (1 << j)][r[j]] = Math.min(dp[i | (1 << j)][r[j]], dp[i][k] + d[k][r[j]]);
				}
			}
		}

		long a = Long.MAX_VALUE;
		for (int i = 0; i < N; i++) {
			a = Math.min(a, dp[(1 << R) - 1][i]);
		}

		System.out.println(a);
	}
}


Measured memory_bytes: 48060
#include<iostream>
#include<set>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<queue>
#include<stdio.h>
#include<math.h>
using namespace std;

#define rep(i,n) for(long long i = 0; i < n; i++)

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

const ll INF = ll(1e18) + 1;

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

ulli gcd(ulli a, ulli b) {
	return (b <= 0) ? a : gcd(b, a % b);
}

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

bool isPrime(int n)
{
	if (n <= 3)return n > 1;
	if (n % 2 == 0)return false;
	if (n % 3 == 0)return false;
	for (int i = 5; i * i < n; i += 6) {
		if (n % i == 0 || n % (i + 2) == 0) { return false; }
	}
	return true;
}
//---------------------------------------------------


void Main()
{
	int n, k, count = 1; cin >> n >> k;
	while (!(n / k == 0)) {
		n /= k;
		count++;
	}
	cout << count << endl;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	Main();
	
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
using namespace std;
typedef long long int ll;
typedef vector<int> vi;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define Sort(a) sort(a.begin(), a.end())
const int INF = 1<<30;
const ll MOD = 1000000007;

int main(void) {

    int n; cin >> n;

    ll sum = (n / 500) * 1000;
    n %= 500;

    sum += (n / 5) * 5;

    cout << sum << endl;
    return 0;

}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n, r;

		while ((n = sc.nextInt()) != 0 && (r = sc.nextInt()) != 0) {
			int[] yama = new int[n];
			for (int i = 0; i < n; i++) {
				yama[i] = n - i;
			}

			for (int j = 0; j < r; j++) {
				int p = sc.nextInt();
				int c = sc.nextInt();
				int[] pyama = new int[p - 1];
				int[] cyama = new int[c];

				for (int i = 0; i < p - 1; i++) {
					pyama[i] = yama[i];
				}
				for (int i = 0; i < c; i++) {
					cyama[i] = yama[i + p - 1];
				}

				for (int i = 0; i < c; i++) {
					yama[i] = cyama[i];
				}
				for (int i = 0; i < p - 1; i++) {
					yama[i + c] = pyama[i];
				}
			}

			System.out.println(yama[0]);
		}
	}
}

Measured memory_bytes: 38628
//自称高知能系Vtuberの高井茅乃です。
//Twitter: https://twitter.com/takaichino
//YouTube: https://www.youtube.com/channel/UCTOxnI3eOI_o1HRgzq-LEZw

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

#define INF 1999999999
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define MODA 1000000007 

int main() {
    int ans = 0;
	int a, b, k, now = 0;
	cin >> a >> b >> k;
	for(int i = 100; i>=1 ; i--){
		if(a%i == 0 && b%i ==0){
			now++;
			if(now == k) ans = i;
		}
	}
    cout << ans << endl;
}

Measured memory_bytes: 256
using System;
namespace ITP1_2_B {
	class Program {
		static void Main(string[] args) {
			string[] s = Console.ReadLine().Split();
			int[] a = new int[3];
			for (int i = 0; i < 3; i++) a[i] = int.Parse(s[i]);
			Array.Sort(a);
			Console.WriteLine(a[0] + " " + a[1] + " " + a[2]);
		}
	}
}

Measured memory_bytes: 9236
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <complex>
#include <string>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <bitset>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#ifndef LOCAL
#define debug(x) ;
#else
#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;

template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &p) {
  out << "{" << p.first << ", " << p.second << "}";
  return out;
}

template <typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  out << '{';
  for (const T &item : v) out << item << ", ";
  out << "\b\b}";
  return out;
}
#endif

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 200010


int main(){
  int A, B;

  cin >> A >> B;

  for (int i=B; i<A+B; i++) {
    int c1 = 1 + i - B;
    int c2 = i / A + i % A;

    if (c1 > c2) {
      printf("%d\n", i);
      return 0;
    }
  }

  puts("-1");

  return 0;
}



Measured memory_bytes: 3208
#include <bits/stdc++.h>
using namespace std;
int main()
{
	vector<int> vec(4, 0);
	int b, a, c;
	while(cin >> a >> b >> c)
	{
		vector<int> v;
		v.push_back(a);
		v.push_back(b);
		v.push_back(c);
		sort(v.begin(), v.end());
		int a1 = v[2] * v[2];
		int b1 = v[1] * v[1];
		int c1 = v[0] * v[0];
		if(!(abs(b - c) < a && a < b + c))
		{
			for(int i = 0; i < 4; i++)
			{
				if(i == 3)
					cout << vec[i] << endl;
				else
					cout << vec[i] << " ";
			}
			return 0;
		}
		vec[0]++;
		if(a1 == b1 + c1)
			vec[1]++;
		else if(a1 < b1 + c1)
			vec[2]++;
		else
			vec[3]++;
	}
}
			


Measured memory_bytes: 3116
#include <iostream>
#include <iomanip>

int main()
{
    int n;
    double a[110];

    std::cin >> n;
    double sum = 0;
    for (int i = 0; i < n; ++i)
    {
        std::cin >> a[i];
        sum += 1/a[i];
    }

    std::cout << std::fixed << std::setprecision(10) << 1/sum;
}


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

using namespace std;
typedef long long ll;

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

  int x; cin >> x;
  vector<int> v;

  for (int i = 0; i < 3; ++i) {
    v.push_back(x % 10);
    x /= 10;
  }

  if (v.front() == v.back()) cout << "Yes" << "\n";
  else cout << "No" << "\n";
}


Measured memory_bytes: 3656
import java.util.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main {

	int INF = 1 << 28;
	int n, m;
	Wall[] walls;
	P t, o;
	void run() {
		Scanner sc = new Scanner (System.in);
		for(;;) {
			n = sc.nextInt();
			if(n==0) break;
			walls = new Wall[n];
			for(int i=0;i<n;i++) walls[i] = new Wall(sc.nextInt(), sc.nextInt(), sc.nextInt());
			m = sc.nextInt();
			for(int i=0;i<m;i++) {
				t = new P(sc.nextInt(), sc.nextInt());
				o = new P(sc.nextInt(), sc.nextInt());
				boolean f = true;
				for(int j=0;j<n;j++) {
					if(distance(t, o, walls[j])) {
						if(clossC(t, o, walls[j])) {
							f = false;
							break;
						}
					}
				}
				if(!f) System.out.println("Safe");
				else System.out.println("Danger");
			}
			
		}
	}
	boolean distance(P p1, P p2, Wall w) {
		int dx = p2.x-p1.x;
		int dy = p2.y-p1.y;
		int line = dx*w.y - dy*w.x + dy*p1.x - dx*p1.y;
		return line * line <= w.r * w.r * (dx*dx+dy*dy);
	}
	
	boolean clossC(P p1, P p2, Wall w) {
		int dx = p2.x-p1.x;
		int dy = p2.y-p1.y;
		int line1 = dy*(p1.y-w.y) + dx*(p1.x-w.x);
		int line2 = dy*(p2.y-w.y) + dx*(p2.x-w.x);
		boolean isIn1 = w.isIn(p1);
		boolean isIn2 = w.isIn(p2);
		if( isIn1 & isIn2 ) return false;
		if( line1 * line2 <= 0 ) return true;
		
		return isIn1^isIn2;
		
	}

	public static void main(String[] args) {
		new Main().run();
	}
	class P {
		int x, y;
		P (int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	class Wall {
		int x, y, r;
		Wall(int x, int y, int r) {
			this.x = x;
			this.y = y;
			this.r = r;
		}
		boolean isIn(P p) {
			return (p.x-x)*(p.x-x) + (p.y-y)*(p.y-y) < r*r;
		}
	}
}

Measured memory_bytes: 12000
#include <bits/stdc++.h>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/integer/common_factor.hpp>
#include <boost/integer/common_factor_rt.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>

using std::string;
using std::vector;
using std::set;
using std::multiset;
using std::unordered_set;
using std::map;
using std::multimap;
using std::unordered_map;
using std::pair;
using std::cin;
using std::cout;

using boost::multiprecision::cpp_int;
using cpp_dec_float_1000 = boost::multiprecision::number<boost::multiprecision::cpp_dec_float<1000, boost::int128_type>>;

typedef uintmax_t    ull;
typedef intmax_t     ll;
typedef uint64_t     ul;
typedef uint32_t     ui;
typedef uint8_t      uc;

constexpr char CRLF  = '\n';
constexpr char SPACE = ' ';
constexpr char VECTOR_COUT_SEPARATOR = SPACE;
constexpr ll INF = 1000'000'007;
constexpr int MOD = 1000'000'007;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> std::ostream& operator<< (std::ostream& os, const std::vector<T>& vc) { for(auto it = vc.begin(); it != vc.end(); ++it) { if (std::next(it) == vc.end()) os << *it; else os << *it << VECTOR_COUT_SEPARATOR; } return os; }
template<class T1, class T2> inline std::ostream & operator<< (std::ostream & os, const std::pair<T1, T2> & p) { return os << p.first << ' ' << p.second; }
template<class T> T modinv(T a, T m) { T b = m, u = 1, v = 0; while (b) { T t = a / b; a -= t * b; boost::swap(a, b); u -= t * v; boost::swap(u, v); } u %= m; if (u < 0) u += m; return u; }
template<class T> inline bool isSosuu(const T& n) { if (n == T(1)) { return false; } for (T i = 2; i*i <= n; ++i) { if (n % i == 0) { return false; } } return true; }
template<class T> vector<vector<T>> split (const vector<T>& S, T delim) { vector<vector<T>> ret{}; vector<T> buff{}; for (auto c : S) { if (c == delim) { if (!buff.empty()) ret.push_back(buff); buff.clear(); } else { buff.push_back(c); } } if (!buff.empty()) ret.push_back(buff); return ret; }
template<class T> inline void printYesNo(const T& t) { cout << (t ? "Yes" : "No") << CRLF; }
template<class T = int64_t> T modpow(T N, T P, T M) { T ret{1}; N %= M; while (P) { if (P & 0x01) { ret *= N; ret %= M; } P >>= 1; N *= N; N %= M; } return ret; }

/** code for assert debug begin */
int gErr = 0;
#define ASSERT(p) if(!(p)){ gErr = 1; }else{ ; }
/** code for assert debug end */

struct Tmp
{
public:
  int N;
  Tmp(int N)
  : N(N)
  {}
};

void solve(void)
{
  int x; cin >> x;
  auto ans = x < 1200;
  cout << (ans ? "ABC" : "ARC") << CRLF;
  return;
}

int main(void)
{
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);

  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++)
#define mfill(x,y) memset(x,y,sizeof(x))
#define all(v) v.begin(), v.end()
#define in(x,y,h,w) if(0<=x&&x<h&&0<=y&&y<w)
#define y0 y12345
#define y1 y54321

#ifdef LOCAL
#define debug(...) fprintf(stderr,__VA_ARGS__)
#else
#define debug(...) 42
#endif

using ul = unsigned long;
using ll = long long;
using P = pair<int, int>;
using vint = vector<int>;using vvint = vector<vector<int>>;
using vll = vector<ll>;using vvll = vector<vector<ll>>;
template<class T>bool chmax(T &a, const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a, const T &b){if(a>b){a=b;return 1;}return 0;}
template <class T>void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
    v.assign(a, vector<T>(b, t));
}
template <class T>T gcd(T &a, T &b){if(a<b){swap(a,b);} T r = a%b; while(r!=0){a=b;b=r;r=a%b;} return b;}

vint dx = {-1, 0, 1, 0}, dy = {0, -1, 0, 1};
vint dx8 = {-1, -1, -1, 0, 1, 1, 1, 0}, dy8 = {-1, 0, 1, 1, 1, 0, -1, -1};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    debug("debug test\n");
    ll n, a, b;cin>>n>>a>>b;
    ll w = (ll)(n/(a+b));
    cout << w*a + min((n-w*(a+b)), a) << endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main{
	public static void main(String[] args){

		Scanner scan = new Scanner(System.in);

		while(true){
			int x = scan.nextInt();
			int y = scan.nextInt();

			if(x == 0 && y == 0){
				break;
			}else{
				if(y < x){
					int a;
					a = x;
					x = y;
					y = a;
					System.out.println(x + " " + y);
				}else{
					System.out.println(x + " " + y);
				}
			}
		}
	}
}

Measured memory_bytes: 35788
#include <bits/stdc++.h>
#define MAX_N 200000
using namespace std;
typedef double dnt;
typedef long long lnt;
template <class T> inline void read(T &x) {
	x = 0; int c = getchar(), f = 1;
	for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
	for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, l, r, s[MAX_N+5]; lnt w, a[MAX_N+5], f[MAX_N+5];
dnt k(int p, int q) {return (dnt)(f[p]-f[q]+a[p]*a[p]-a[q]*a[q])/(dnt)(a[p]-a[q])/2;}
int main() {
	read(n), read(w), s[0] = 1;
	for (int i = 1; i <= n; i++) read(a[i]);
	for (int i = 2; i <= n; s[++r] = i++) {
		while (l < r && k(s[l+1], s[l]) <= (dnt)a[i]) l++;
		f[i] = f[s[l]]+(a[i]-a[s[l]])*(a[i]-a[s[l]])+w;
		while (l < r && k(s[r], s[r-1]) >= k(i, s[r])) r--;
	}
	return printf("%lld\n", f[n]), 0;
}


Measured memory_bytes: 4096
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  long long int p, k, d;
  cin >> p >> k >> d;
  long long int x = abs(p);
  long long int a = x/d;
  long long int ans = 0;
  if(a >= k) ans = x-k*d;
  else if((k-a)%2 == 1) ans = abs(x-(a+1)*d);
  else ans = x-a*d;
  cout << ans << endl;
}

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


/*
    Iterative Square Method
        find the pow(x, n) (mod m)
*/


long long modpow(long long x, long long n, long long m = 1e9+7) {
    if (n == 0) return 1;
    if (n % 2 == 1) return (x * modpow(x, n - 1, m)) % m;
    long long t = modpow(x, n / 2, m);
    return (t * t) % m;
}



int main() {
    long long x, n;
    cin >> x >> n;
    
    cout << modpow(x, n) << endl;
    return 0;
}


Measured memory_bytes: 3100
#include<bits/stdc++.h>
using namespace std;
int main(){
	int N=0;
	int digits[3];
	scanf("%i",&N);
	if(N>=100 && N<=999){
		int i=0;
		while(N>0){
			digits[i]=N-(N/10)*10;
			N=N/10;
			i++;
		}
		for(int j=0;j<=3/2;j++){
			if(digits[j]!=digits[2-j]){
				printf("No");
				return 0;
			}
		}
		printf("Yes");
	}
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
    int a,b,c;
    int ans = 0;

    scanf("%d %d %d", &a, &b, &c);

    ans = a+b;
    if(ans >= b+c) {
        ans = b+c;
    }
    if(ans >= c+a) {
        ans = c+a;
    }

    printf("%d\n", ans);
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define loop(i,x,z) for (int i=x;i<z;i++)
using ll = long long;
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
typedef pair<int, int> pii;
const ll M = 1000000007;
typedef int item;
int main()
{
	int n;
	cin>>n;
	n^=1;
	cout<<n;
}

Measured memory_bytes: 3608
#include <iostream>
#include <sstream>
#include <string>
#include <cassert>
#include <cmath>
#include <climits>
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <functional>
#include <numeric>
#include <iomanip>

using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i,a,b) for(int i = (a); i < (int)(b); ++i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(v) ((int)v.size())

#define pb push_back
#define mp make_pair
#define mt make_tuple

ll N, M;
vector<ll> As;
vector<ll> sumA;

// 値がsum以上のマスが何個あるか？
ll count_pair_num(ll sum) {
    ll ret = 0;
    for(auto a: As) {
        auto it = lower_bound(ALL(As), sum - a);
        ret += N - (it - As.begin());
    }
    return ret;
}

// 値がsum以上のマスがpair_num個以上あるか？
bool check(ll sum, ll pair_num) {
    return count_pair_num(sum) >= pair_num;
}

// 値がsum以下のマスの値の合計
ll count_sum(ll num) {
    ll ret = 0;
    for(auto a: As) {
        auto it = lower_bound(ALL(As), num - a);
        if (it != As.end()) {
            auto tmp1 = sumA[it - As.begin()];
            auto tmp2 = (As.end() - it);
            ret += tmp1 + a * tmp2;
        }
    }
    return ret;
}

int main(void)
{
    cin.sync_with_stdio(false);

    cin >> N >> M;
    As.resize(N);
    REP(n, N) cin >> As[n];
    sort(ALL(As));
    sumA.resize(N);
    REP(n, N) {
        if (n == 0) sumA[N - n - 1] = As[N - n - 1];
        else sumA[N - n - 1] = sumA[N - n] + As[N - n - 1];
    }

    ll ok = 0;
    ll ng = As[N-1] * 2 + 1; // 最初 As[N-1] * 2 にしててエラー; 確実に境界をみつけるためには+1が必要
    while (ng - ok > 1) {
        auto mid = (ok + ng) / 2;
        if (check(mid, M)) {
            ok = mid;
        } else {
            ng = mid;
        }
    }
    auto pair_num = count_pair_num(ok);
    
    ll ans = count_sum(ok + 1);
    auto pair_num2 = count_pair_num(ok + 1);
    ans += (M - pair_num2) * ok;
    cout << ans << endl;

    return 0;
}



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

using namespace std;

using ll = long long;
using Vi = vector<int>;
using Vl = vector<ll>;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

constexpr int I_INF = (1 << 30);
constexpr ll L_INF = (1ll << 62);

//==================================

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

    int N;
    cin >> N;

    vector<string> S(N);
    vector<int> T(N);

    for (int i = 0; i < N; ++i) {
        cin >> S[i] >> T[i];
    }

    string X;
    cin >> X;

    int ans = 0;
    bool on = false;

    for (int i = 0; i < N; ++i) {
        if (on) {
            ans += T[i];
        }
        if (S[i] == X) on = true;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define gmax(x,y) x=max(x,y)
using namespace std;

const int MOD = 1e9 + 7; 
typedef long long ll;

int mul(int x,int y){
	return (1LL*x*y) % MOD;
}

int modpow(int x,int p){
	int res = 1;
	while(p){
		if(p&1)res = mul(res,x);
		x = mul(x,x);
		p/=2;
	}
	return res;
}

int inv(int x){
	return modpow(x, MOD - 2);
}

int add(int x,int y){
	return (x + y) % MOD;
}

const int N = 1e6 + 5;

int cnt[N];

int main(){
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);
	int n;
	cin >> n;
	vector<ll> a(n);
	for(int i = 0;i < n; ++i){
		cin >> a[i];	
		int x = a[i];
		for(int d = 2; d * d <= x; ++d){
			int tcnt = 0;
			while(x % d == 0){
				++tcnt;	
				x/=d;
			}
			gmax(cnt[d], tcnt);
		}
		if(x != 1){
			gmax(cnt[x], 1);	
		}
	}
	int lcm = 1;
	for(int i = 2;i < N; ++i){
		lcm = mul(lcm, modpow(i,cnt[i]));
	}
	int ans = 0;
	for(int i = 0;i < n; ++i){
		ans = add(ans, mul(lcm, inv(a[i])));
	}
	cout << ans << '\n';
}


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

int main(){
    long long N;
    cin >> N;
    long long A;
    vector<pair<long long, long long> > val_index;
    val_index.push_back(make_pair(-1,-1));
    for(long long i=0; i<N; i++){
        cin >> A;
        val_index.push_back(make_pair(A,i+1));
    }
    sort(val_index.begin(),val_index.end());
    long long dp[N+1][N+1];
    dp[1][0] = val_index[N].first*abs(val_index[N].second-1);
    dp[0][1] = val_index[N].first*abs(N-val_index[N].second);
    for(long long i=2; i<=N; i++){
        for(long long j = 0; j<=i; j++){
            if(j==0){
                dp[i][0] = dp[i-1][0] + val_index[N+1-i].first*abs(val_index[N+1-i].second-i);
            }else if(j==i){
                dp[0][i] = dp[0][i-1] + val_index[N+1-i].first*abs((N+1-i)-val_index[N+1-i].second);
            }else{
                dp[i-j][j] =max(dp[i-j-1][j] + val_index[N+1-i].first*abs(val_index[N+1-i].second-(i-j)),dp[i-j][j-1] + val_index[N+1-i].first*abs((N+1-j)-val_index[N+1-i].second));
            }
        }
    }

    long long ans = 0;
    for(long long j=0; j<=N; j++){
        ans = max(ans,dp[N-j][j]);
    }
    cout << ans << endl;
    system("pause");
    return 0;
}

Measured memory_bytes: 26396
def solve(n, a, b):
  ab = [(ai, bi) for ai, bi in zip(a, b) if ai < bi]
  if len(ab) == 0:
    return n
  elif len(ab) == 1:
    a0, b0 = ab[0]
    return (n//a0)*b0 + n%a0
  elif len(ab) == 2:
    (a0, b0), (a1, b1) = ab
    if b0/a0 < b1/a1:
      a0, b0, a1, b1 = a1, b1, a0, b0
    return max(((n-a1*i)//a0)*b0 + (n-a1*i)%a0 + i*b1 for i in range(a0))
  else:
    dp = [j for j in range(n+1)]
    for ai, bi in ab:
      for j in range(ai, n+1):
        dp[j] = max(dp[j], dp[j-ai]+bi)
    return dp[-1]

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

N = solve(N, A, B)
N = solve(N, B, A)
print(N)

Measured memory_bytes: 3188
#include <stdio.h>

int main(void) {
	int N, K, X, Y, fee = 0;
	
	scanf("%d %d %d %d", &N, &K, &X, &Y);
	
	for (int i = 0; i < N; i++) {
		if (K > 0) {
			fee += X;
			K--;
		} else {
			fee += Y;
		}
	}
	
	printf("%d", fee);
	
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define krep(i,k,n,m) for(int i=k;i<n;i+=m)
#define erep(i,k,n) for(int i=k;i<n;i++)
#define mod 1000000007;
//最大公約数
int gcd(int s,int b){
    if(b==0)return s;
    return gcd(b,s%b);
}
signed main() {
    int n,k;
    cin>>n>>k;
    int a[n];
    rep(i,n){
        cin>>a[i];
    }
    if((n-1)%(k-1)==0){
        cout<<(n-1)/(k-1)<<endl;
    }
    else{
        cout<<(n-1)/(k-1)+1<<endl;
    }
}

Measured memory_bytes: 1024
import sys
import math
from collections import Counter

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

set_A = set(A)
set_flag = len(set_A) != N

counter = Counter(A)
if len(counter) == N or (1 in counter and len(counter) - 1 + counter[1] == N):
    co_prime = True
    max_a = max(A)
    
    coprime = True
    exists = set()
    for i in range(2, max_a + 1):
        flag = False
        for j in range(i, max_a + 1, i):
            if j in set_A:
                if not flag:
                    flag = True
                elif flag:
                    coprime = False
                    break
        if not coprime:
            break
else:
    coprime = False

pairwise = coprime
if pairwise:
    print("pairwise coprime")
    sys.exit()

setwise = False
tmp = A[0]
for i in range(N):
    tmp = math.gcd(tmp, A[i])
if tmp == 1:
    setwise = True

if setwise:
    print("setwise coprime")
else:
    print("not coprime")

Measured memory_bytes: 226524
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,b) FOR(i,0,b)
#define INF 1e9

int main(){
  int a, b, c, x, ans = 0;

  cin>>a>>b>>c>>x;

  if (a * 500 > x) a = x / 500 + 1;
  if (b * 100 > x) b = x / 100 + 1;
  if (c * 50 > x) c = x / 50 + 1;

  REP (i,a+1) {
    REP (j,b+1) {
      REP (k,c+1) {
        int x_tmp = x;

        x_tmp = x_tmp - 500 * i;
        x_tmp = x_tmp - 100 * j;
        x_tmp = x_tmp - 50 * k;

        if (x_tmp == 0) ans++;
      }
    }
  }

  cout<<ans<<endl;

  return 0;
}


Measured memory_bytes: 256
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

public class Main {
	public static void main(String[] args) {
		Map<String,Integer> set = new HashMap<>(); 
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		String old = null;
		for (int i=0;i<n;i++) {
			String moi = sc.next();
			if (old==null) {
			} else {
				if (old.charAt(old.length()-1)!=moi.charAt(0)) {
					System.out.println("No");
					return;
				}
				if (set.get(moi)!=null) {
					System.out.println("No");
					return;
				}
				
			}
			old = moi;
			set.put(moi,1);
		}
		System.out.println("Yes");
	}
}


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

int main() {
  int n, m;
  cin >> n >> m;
  vector<P> vec(n);
  rep(i,n) cin >> vec.at(i).first >> vec.at(i).second;
  sort(vec.begin(), vec.end());
  ll sum = 0;
  ll ans = 0;
  rep(i,n) {
    if(sum + vec.at(i).second <= m) {
      sum += vec.at(i).second;
      ans += (vec.at(i).first * vec.at(i).second);
    }
    else {
      ans += (vec.at(i).first * (m-sum));
      break;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1792
#include <stdio.h>
#include <string.h>

int main(void)
{
    int i = 0, j;

    char word_list[501][33];
    while (scanf("%s", word_list[i]) != EOF) {
        i++;
    }
    int word_num = i;

    int word_cnt[501] = {0};
    int len;
    int longest_len = 0;
    char longest_word[33];
    for (i = 0; i < word_num; i++) {
        len = strlen(word_list[i]);
        if (len > longest_len) {
            longest_len = len;
            strcpy(longest_word, word_list[i]);
        }
        for (j = 0; j < i; j++) {
            if (strcmp(word_list[i], word_list[j]) == 0) {
                word_cnt[i]++;
            }
        }
    }

    int cnt_max = 0;
    char mode_word[33];
    for (i = 0; i < word_num; i++) {
        if (word_cnt[i] > cnt_max) {
            cnt_max = word_cnt[i];
            strcpy(mode_word, word_list[i]);
        }
    }

    printf("%s %s\n", mode_word, longest_word);

    return 0;
}

Measured memory_bytes: 576
def judge(a,b,c,d,e,k):
    if abs(a - b) > k:
        return False
    if abs(a - c) > k:
        return False
    if abs(a - d) > k:
        return False
    if abs(a - e) > k:
        return False
    if abs(b - c) > k:
        return False
    if abs(b - d) > k:
        return False
    if abs(b - e) > k:
        return False
    if abs(c - d) > k:
        return False
    if abs(c - e) > k:
        return False
    if abs(d - e) > k:
        return False
    return True


def main():
    a = int(input())
    b = int(input())
    c = int(input())
    d = int(input())
    e = int(input())
    k = int(input())
    if judge(a,b,c,d,e,k):
        print('Yay!')
    else:
        print(':(')

main()


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
 
#define rep(i,j,n) for(int i=j;i<n;++i)
#define all(i) i.begin(),i.end()
#define rall(i) i.rbegin(), i.rend()
#define INF 1e9
#define LINF 1e18
const int mod = 1e9 + 7;
 
typedef long long i64;
typedef pair<int, int> pi;
 
template <class T> using vt = vector<T>;
template <class T> using vvt = vector<vector<T>>;
 
i64 gcd(i64 n, i64 m) {return (m == 0? n : gcd(m, n % m));}
i64 lcm(i64 n, i64 m) {return (n / gcd(n, m) * m);}
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

class BipartiteMatching {
  private:
    std::vector<std::vector<int>> graph;
    std::vector<int> match;
    std::vector<bool> used;

    bool dfs(int v) {
      used[v] = true;

      for(auto &e : graph[v]) {
        int m = match[e];

        if(m < 0 || (!used[m] && dfs(m))) {
          match[v] = e;
          match[e] = v;
          return true;
        }
      }
      return false;
    }

  public:
    BipartiteMatching(int v) {
      graph = std::vector<std::vector<int>>(v);
      match = std::vector<int>(v, -1);
      used = std::vector<bool>(v);
    }

    void add_edge(int u, int v) {
      graph[u].push_back(v);
      graph[v].push_back(u);
    }

    int bipartite_matching() {
      int res = 0;

      for(int v = 0; v < graph.size(); ++v) {
        if(match[v] < 0) {
          used.assign(used.size(), false);
          if(dfs(v)) res++;
        }
      }
      return res;
    }
};
 
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int m, n;
  while(cin >> m >> n, m != 0 && n != 0) {
    BipartiteMatching bm(m + n);
    vt<int> b(m), r(n);
    rep(i, 0, m) cin >> b[i];
    rep(i, 0, n) cin >> r[i];

    rep(i, 0, m) {
      rep(j, 0, n) {
        if(gcd(b[i], r[j]) > 1) bm.add_edge(i, m + j);
      }
    }
    cout << bm.bipartite_matching() << endl;
  }
}


Measured memory_bytes: 4452