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

typedef ostringstream OSS;
typedef istringstream ISS;

typedef long long LL;
typedef pair<int, int> PII;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
typedef vector<string> VS;
typedef vector<VS> VVS;
typedef vector<bool> VB;
typedef vector<VB> VVB;
typedef vector<PII> VPII;

#define fst first
#define snd second
#define MP make_pair
#define PB push_back
#define EB emplace_back 
#define ALL(x) (x).begin(),(x).end()
#define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))
#define DUMP( x ) cerr << #x << " = " << ( x ) << endl

template < typename T > inline T fromString(const string &s) { T res; ISS iss(s); iss >> res; return res; };
template < typename T > inline string toString(const T &a) { OSS oss; oss << a; return oss.str(); };

const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};

struct Edge {
    Edge(int t, int c) : to(t), cost(c) {}
    int to, cost;
};

struct Vertex {
    Vertex(){}
    Vertex(int v, int h, int c) : vi(v), hp(h), cost(c) {}
    int vi, hp, cost;

    bool operator > (const Vertex &v) const {
        return cost > v.cost;
    }
};

int main(void) {
    int V, M, L, E, S, G;
    while (cin >> V >> M >> L >> E >> S >> G, V) {
        VB ls(V);
        for (int i = 0; i < L; i++) {
            int l;
            cin >> l;
            ls[l] = true;
        }

        vector<vector<Edge>> es(V);
        for (int i = 0; i < E; i++) {
            int f, t, c;
            cin >> f >> t >> c;
            es[f].EB(t, c);
            es[t].EB(f, c);
        }

        VVI distance(V, VI(M + 1, INF));
        distance[S][M] = 0;

        priority_queue<Vertex, vector<Vertex>, greater<Vertex>> que;
        que.push(Vertex(S, M, 0));

        while (que.size()) {
            auto cur = que.top();
            que.pop();

            if (cur.cost > distance[cur.vi][cur.hp]) continue;

            for (auto &e : es[cur.vi]) {
                int hp = cur.hp - e.cost;
                if (hp < 0) continue;

                int &dist = distance[e.to][hp];
                int cost = cur.cost + e.cost;
                if (dist > cost) {
                    dist = cost;
                    que.push(Vertex(e.to, hp, cost));
                }
            }

            if (ls[cur.vi]) {
                for (int i = cur.hp; i <= M; i++) {
                    int cost = cur.cost + i - cur.hp;
                    int &dist = distance[cur.vi][i];
                    if (dist > cost) {
                        dist = cost;
                        que.push(Vertex(cur.vi, i, cost));
                    }
                }
            }
        }

        int ans = *min_element(ALL(distance[G]));
        if (ans != INF) {
            cout << ans << endl;
        } else {
            cout << "Help!" << endl;
        }
    }

	return 0;
}

Measured memory_bytes: 1468
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <map>
#include <string>
#include <queue>
#include <stack>
#include <math.h>
#include <cmath>
#include <numeric>
#include <iomanip>


#define log(x) cout<<x<<endl
#define pb push_back
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
typedef long long lint;
using namespace std;


// <<fixed<<setprecision(6)<<


int gcd(lint x, lint y){
  return y==0 ? x:gcd(y,x % y);
}


int digsum(int n) {
  int res = 0;
  while(n > 0) {
    res += n%10;
    n /= 10;
  }
  return res;
}


int dignum(int n) {
  int res = 0;
  while(n > 0) {
    res++;
    n /= 10;
  }
  return res;
}


int stringcount(string s, char c) {
  return count(s.cbegin(), s.cend(), c);
}


int lcm(lint x, lint y){
  return x/ gcd(x, y) * y;
}


int combi(int n, int r){
  int num = 1;
  for(int i = 1; i <= r; i++){
    num = num * (n - i + 1) / i;
  }
  return num;
}


int main(){
  lint n,y;
  lint z=0;
  bool isyes=false;
  cin>>n>>y;
  for(int i=0;i<=n;i++){
    for(int j=0;j<=n;j++){
      z=n-i-j;
      if(10000*i+5000*j+1000*z==y&&z>=0){
        cout<<i<<" "<<j<<" "<<z;
        i=100000000;
        isyes=true;
        break;
        break;
      }
    }
  }
  if(isyes==false){
    cout<<"-1"<<" "<<"-1"<<" "<<"-1";
  }
}

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

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

	set<int> existingColors;
	int freeColors = 0;
	while(N--){
		int a; cin>>a;
		int b = a/400;
		if(b < 8) existingColors.insert(b);
		else freeColors++;
	}

	int minC = max(1, (int)existingColors.size());
	int maxC = existingColors.size() + freeColors;
	printf("%d %d\n", minC, maxC);
}

Measured memory_bytes: 256
import * as fs from "fs";

const input = fs.readFileSync("/dev/stdin", "utf8").split(/\n/);
const N: number = +input[0];
const strings = input[1];
let count = 0;
for (let i = 0; i < N; i++) {
  if (strings[i] !== strings[i + 1]) {
    count++;
  }
}
console.log(count);

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

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

	int H, W;
	cin >> H >> W;
	char a[100][100];
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			cin >> a[i][j];
		}
	}
	for (int i = 0; i < W+2; i++) {
		cout << "#";
	}
	cout << endl;
	for (int i = 0; i < H; i++) {
		cout << "#";
		for (int j = 0; j < W; j++) {
			cout << a[i][j];
		}
		cout<<"#"<<endl;
	}
	for (int i = 0; i < W + 2; i++) {
		cout << "#";
	}
	cout << endl;
	
}


Measured memory_bytes: 256
n, A, B, C = map(int, input().split())

l = [0 for _ in range(n)]

for i in range(n):
    l[i] = int(input())


def dfs(count, a, b, c):
    if count == n:
        if a == 0 or b == 0 or c == 0:
            return 10000000
        return abs(A - a) + abs(B - b) + abs(C - c) - 30
    else:
        return min(dfs(count + 1, a, b, c),
                   dfs(count + 1, a + l[count], b, c) + 10,
                   dfs(count + 1, a, b + l[count], c) + 10,
                   dfs(count + 1, a, b, c + l[count]) + 10,
                   )


print(dfs(0, 0, 0, 0))

Measured memory_bytes: 3064
#include <stdio.h>
#define N 2000000
#define I 10000
int a[N+1],b[N+1],c[N+1];
main(){
   
  int n,i,j,k;
  
  scanf("%d",&n);
  
   
  for(i=0; i<n; i++){
    scanf("%d",&a[i+1]);
    if(a[i]<a[i+1])
      k=a[i];
  }
   
  for(i=0; i<n; i++)
    c[i]=0;
   
   
  for(i=0; i<n; i++)
    c[a[i+1]]++;
  
   
  for(i=0; i<N; i++)
    c[i+1]=c[i+1]+c[i];
   
   
  for(i=n; i>0; i--){
    b[c[a[i]]]=a[i];
    c[a[i]]--;
  }
   
   
  for(i=0; i<n-1; i++)
    printf("%d ",b[i+1]);
  printf("%d\n",b[n]);
   
 
  return 0;
}

Measured memory_bytes: 24036
#include <bits/stdc++.h>
#define ll long long int
#define ld long double
#define pb push_back
#define mp make_pair
#define all(a) a.begin(), a.end()
#define X first
#define Y second
#define sz(x) (int)x.size()
#define el '\n'
#define M 10e9 + 7 
using namespace std;
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n ,k;
  cin>>n>>k;
  string s;
  cin>>s;
  s[k-1]=s[k-1]+32;
  cout<<s<<el;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <time.h>

#define loop(i, num)  for (int i = 0; i < num; i++)

using namespace std;

int n, ans;

vector<int> nums;

int main() {
    
    cin >> n;
    
    nums.resize(n);
    
    loop (i, n) {
        
        cin >> nums[i];
        
    }
    
    for (int i = 0; i < n - 1; i++) {
        
        if (nums[i] == i + 1) {
            
            swap(nums[i], nums[i + 1]);
            
            ++ans;
            
            ++i;
            
        }
        
    }
    
    if (nums[n - 1] == n) {
        
        ++ans;
        
    }
    
    cout << ans << endl;
    
}


Measured memory_bytes: 640
n , m = map(int,input().split())
l=[]
r=[]
for i in range(m):
    x , y = map(int,input().split())
    l.append(x)
    r.append(y)

a = max(l)
b = min(r)
if a > b:
    print(0)
else:
    print(b-a+1)

Measured memory_bytes: 11016
#include<iostream>
#include<string>
#include<vector>
#include<list>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<set>
#include<map>
#include<queue>
#include<cstring>
#include<sstream>
using namespace std;

typedef long long ll;

int main() {
  int N; cin >> N;
  vector<int>A(N+1);
  vector<ll>sum(N+1);
  sum[0] = 0;
  for ( int i = 1; i <= N; i++ ) cin >> A[i];

  for ( int i = 1; i <= N; i++ ) {
    sum[i] = sum[i-1]+A[i];
  }
  
  sort(sum.begin(),sum.end());
  /*  sum.push_back(1e18);
  ll cnt = 1;
  ll ans = 0;
  for ( int i = 1; i < sum.size(); i++ ) {
    if ( sum[i] == sum[i-1] ) cnt++;
    else {
      ans += cnt*(cnt-1)/2;
      cnt = 1;
    }
  }
  */

  map<ll,ll> mp;
  for ( int i = 0; i <= N; i++ ) {
    mp[sum[i]]++;
  }
  ll ans = 0;
  map<ll,ll>::iterator ite;
  for ( auto ite = mp.begin(); ite != mp.end(); ite++ ) {
    //cout << ite->first << " " << ite->second << endl;
    if (ite->second >= 2) ans += ite->second*(ite->second-1)/2;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 15104
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define int long long
using namespace std;
typedef vector<int>   vint;
typedef pair<int,int> pint;

int dy[4]={-1,0,0,1};
int dx[4]={0,-1,1,0};

signed main()
{
    int H,W; cin>>H>>W;
    vector<string> s(H);
    REP(i,H) cin>>s[i];

    REP(i,H) REP(j,W){
        if(s[i][j]=='.') continue;
        bool ok=false;
        REP(k,4){
            int y=i+dy[k];
            int x=j+dx[k];
            if(y<0 or y>=H or x<0 or x>=W) continue;
            if(s[y][x]=='#') ok=true;
        }
        if(!ok){
            cout<<"No"<<endl;
            return 0;
        }
    }
    cout<<"Yes"<<endl;
}

Measured memory_bytes: 256
s=input()
if(len(s)>9):
    print("NO")
    quit()
i=0
for c in "AKIHABAR":
    if(len(s)==i):
      print("NO")
      quit()
    if(s[i]==c):
        i+=1
    else:
        if(c!="A"):
            print("NO")
            quit()
print("YES")

Measured memory_bytes: 3060
# optimize output length

Q=[]
A=->*x{Q<<[?+,*x]*" "}
C=->*x{Q<<[?<,*x]*" "}

C[2,1,6]
0.upto(28){|i|
 A[6+i,6+i,7+i]
}

29.downto(0){|i|
 A[6+i,4,3]
 C[0,3,36+i]
 if i>0
  C[36+i,6,3]
  i.times{A[3,3,3]}
  A[3,4,4]
 end
}

A[1,6,1]
29.downto(0){|i|
 A[6+i,5,3]
 C[3,1,66+i]
 if i>0
  A[66+i,66+i,3]
  (i-1).times{A[3,3,3]}
  A[3,5,5]
 end
}

58.downto(0){|k|
 [k-29,0].max.upto([k,29].min){|i|
  j=k-i
  C[36+i,66+j,3]
  A[2,3,2]
 }
 A[2,2,2] if k>0
}

puts Q.size,Q

Measured memory_bytes: 14488
#include <stdio.h>

long long int checks[1000000];

int main() {
    long long int N, res = 0;
    scanf("%lld", &N);

    int pos = 0;
    long long int x = 1, sum = 0;
    while (pos < 1000000) {
        sum += x;
        x++;
        checks[pos++] = sum;
    }

    for (long long int i = 2; i * i <= N; i++) {
        if (N % i != 0) continue;

        long long int acc = 0;
        while(N % i == 0) {
            acc++;
            N /= i;
        }

        for (pos = 0; pos < 1000000; pos++) {
            if (acc < checks[pos]) {
                res += pos;
                break;
            }
        }
    }

    if (N != 1) res++;

    printf("%lld\n", res);
}


Measured memory_bytes: 9548
#include <bits/stdc++.h>
#include <set>
#include <numeric>
#define rep(i,n) for (int i=0; i < (n); ++i)
#define all(a) a.begin(), a.end()
using ll = long long;
using namespace std;
 
// ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }


// const double PI = acos(-1);
// int gcd(int x, int y) { return (x % y)? gcd(y, x % y): y; }
// int a[12][12];

void solve() {
  string s;
  cin >> s;
  if (s[1] == 'B') cout << "ARC" << endl;
  else cout << "ABC" << endl;
}


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


Measured memory_bytes: 3612
n=int(input())

def digitSum(n):
    # 数値を文字列に変換
    s = str(n)
    # １文字ずつ数値化し配列にする。
    array = list(map(int, s))
    # 合計値を返す
    return sum(array)

if digitSum(n)%9 == 0:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 79620
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repo(i,n) for(int i = 1; i < (int)(n); i++)
#define pb push_back
#define mp make_pair
#define np next_permutation
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define mod 1000000007
#define pi acos(-1.0)
const ll INF = 1LL<<61;
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }
ll jou(ll N, ll P){if(P==0) return 1;
  if(P%2==0){ll t = jou(N, P/2);return t*t % mod;
  }return (N * jou(N, P-1)) % mod;}  //jou(n,mod-2)で逆元
//intの最大値2147483647 ≒ 2×10^9
//long longの最大値9223372036854775807 ≒ 9×10^18
//'大文字'+=32;    で小文字に
//  cout << fixed << setprecision (20);   小数点以下2０桁まで
//実行時間制約2秒では２×10^8回くらいまで計算できる




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

  vector<int> p(n,1);
  vector<bool> q(n,false);
  int now=0;
  q[0]=true;
  rep(i,m){
    int a,b;
    cin>>a>>b;
      if(q[a-1]){
        if(p[a-1]==1) q[a-1]=false;
        q[b-1]=true;
      }
    p[a-1]--;
    p[b-1]++;
  }

  int ans=0;
  rep(i,n){
    if(q[i])ans++;
  }

  cout << ans << endl;

}

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

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i,n) cin >> a.at(i);
  sort(a.begin(),a.end());
  int sum = 0;
  rep(i,n-1) sum+=a.at(i);
  if(a.at(n-1) < sum) cout << "Yes" << endl;
  else cout << "No" << endl ;
 }


Measured memory_bytes: 256
s = input()
n = len(s)

flag = [0] * 3

if s == s[::-1]:
    flag[0] = 1

a = int((n - 1) * 0.5)
sa = s[:a]
if sa == sa[::-1]:
    flag[1] = 1

b = int((n + 3) * 0.5)
sb = s[(b - 1):]
if sb == sb[::-1]:
    flag[2] = 1

if sum(flag) == 3:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
//
// Created by Myabu on 2020/01/26.
//

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <utility>
#include <math.h>
#include <stack>
#include <queue>
#include <cstdio>
#include <numeric>
#include <iomanip>

using namespace std;


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

    long long ans = 0;
    for (int i = 0; i < N; ++i) {
        int x,y;
        cin>>x>>y;
        
        ans += abs(x-y)+1;
    }
    
    cout<<ans<<endl;


    return 0;
}

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

using namespace std;


vector< pair<ll,ll> >vt[sz];

string ss[sz];

string tani(ll x)
{
    string s="",ss="";

    ll a,b,n,k,p,d,c=0;

    while(x>0)
    {
        p=x%10;
        c++;
        x=x/10;
        s+=(p+'0');

    }
    d=6-c;

    for(ll i=1;i<=d;i++)ss+="0";

    reverse(s.begin(),s.end());

    ss+=s;

    return ss;
}

int main()
{


    ll n,m,a,b,p,i,j,k;

    cin>>n>>m;

    string x,y;


    for(i=1; i<=m; i++)
    {
        cin>>a>>b;

        vt[a].push_back({b,i});
    }

    for(i=1;i<=n;i++)
    {
        sort(vt[i].begin(),vt[i].end());

        for(j=0;j<vt[i].size();j++)
        {
            x=tani(i);
            y=tani(j+1);
            x+=y;
            p=vt[i][j].second;
            ss[p]=x;

        }
    }

    for(i=1;i<=m;i++)cout<<ss[i]<<endl;

    return 0;

}


Measured memory_bytes: 15872
import java.awt.Point;
import java.util.ArrayDeque;
import java.util.Scanner;
//https://abc007.contest.atcoder.jp/submissions/1889827
public class Main {
	static final int[] dx={0,1,0,-1}, dy={-1,0,1,0};
	public static void main(String[] args) {
		final Scanner sc = new Scanner(System.in);
		int h = sc.nextInt() + 2;
		int w = sc.nextInt() + 2;
		Point start = new Point(1, 1);
		Point goal = new Point(h-2, w-2);
		int all = 0;
		char[][] map = new char[h][w];
		StringBuilder sb = new StringBuilder();
		for(int i = 0; i < w; i++) sb.append('#');
		map[0]=sb.toString().toCharArray();
		map[h-1]=sb.toString().toCharArray();
		for (int i = 1; i < h-1; i++) {
			map[i] = ("#"+sc.next()+"#").toCharArray();
			for(int j = 1; j < w-1; j++) {
				if(map[i][j] == '.') all++;
			}
		}
		ArrayDeque<Point> deque = new ArrayDeque<>();
		deque.add(start);
		int count = 0;
		map[1][1] = '#';
		int nx, ny;
		outer:for(;true;count++) {
			for(int i = deque.size(); i > 0; i--) {
				Point poll = deque.poll();
				if(poll.equals(goal)) {
					break outer;
				}
				if(count > 2600) {
					System.out.println(-1);
					return;
				}
				for(int j = 0; j < 4; j++) {
					nx = poll.x+dx[j];
					ny = poll.y+dy[j];
					if(map[nx][ny] == '.') {
						deque.add(new Point(nx,ny));
						map[nx][ny] = '#';
					}
				}
			}
			if(deque.isEmpty()) {
				System.out.println(-1);
				return;
			}
		}
		System.out.println(all - count - 1);
	}
}

Measured memory_bytes: 23764
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <functional>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <cassert>
#include <exception>
using namespace std;
  
int main(){
  int n,m,x;
  int A[110]={};
  cin >> n >> m >> x;
  for(int i=0; i<m; i++){
    int l;
    cin >> l;
    A[l] = 1;
  }
  int ans1 = 0;
  for(int i=0; i<x; i++){
    ans1 += A[i];
  }
  int ans2 = 0;
  for(int i=x+1; i<n; i++){
    ans2 += A[i];
  }
  

  cout << min(ans1,ans2) << endl;
  

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <map>
#include <string>

using namespace std;

map<string, int> cnt;
string max_str;
int num_max;
int main() {
    string str;
    while (cin >> str) {
        cnt[str]++;
        num_max = max(num_max, cnt[str]);
        if (max_str.size() < str.size()) {
            max_str = str;
        }
    }

    for (auto e : cnt) {
        if (e.second == num_max) {
            cout << e.first << " ";
        }
    }
    cout << max_str << endl;
}

Measured memory_bytes: 3052
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main() {
    int n, m;
    cin >> n >> m;
    vector<P> p(m);
    
    rep(i,m) cin >> p[i].first >> p[i].second;
    rep(x,1000) {
        int keta = 1;
        int nx = x/10;
        vector<int> d(1,x%10);
        while (nx) {
            keta++;
            d.push_back(nx%10);
            nx /= 10;
        }
        if (keta != n) continue;
        bool ok = true;
        reverse(d.begin(), d.end());
        rep(i,m) {
            if (d[p[i].first-1] != p[i].second) ok = false;
        }
        if (ok) {
            cout << x << endl;
            return 0;
        }
    }
    cout << -1 << endl;
    return 0;
}




Measured memory_bytes: 256
//https://atcoder.jp/contests/dp/tasks/dp_n
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#ifdef BTK
#define DEBUG if(1)
#else
#define CIN_ONLY if(1)
struct cww {cww() {CIN_ONLY{ios::sync_with_stdio(false); cin.tie(0);}}}star;
#define DEBUG if(0)
#endif
#define ALL(v) (v).begin(),(v).end()
#define REC(ret, ...) std::function<ret (__VA_ARGS__)>
template <typename T>inline bool chmin(T &l, T r){bool a = l>r; if (a)l = r; return a;}
template <typename T>inline bool chmax(T &l, T r){bool a = l<r; if (a)l = r; return a;}
template <typename T>istream& operator>>(istream &is, vector<T> &v){for (auto &it : v)is >> it;return is;}
class range {private: struct I { int x; int operator*() { return x; }bool operator!=(I& lhs) { return x<lhs.x; }void operator++() { ++x; } }; I i, n;public:range(int n) :i({ 0 }), n({ n }) {}range(int i, int n) :i({ i }), n({ n }) {}I& begin() { return i; }I& end() { return n; }};

int N;
LL dp[412][412];
LL a[412];
LL as[412];
int main(){
    cin>>N;
    for(int i:range(N)){
        cin>>a[i];
        as[i+1]=a[i]+as[i];
    }
    for(int i:range(412))for(int j:range(412))dp[i][j]=1e17;
    for(int i:range(N))dp[i][i+1]=0;
    for(int len:range(1,N+1)){
        for(int i:range(N)){
            int j = i+len;
            if(j>N)continue;
            for(int k:range(i+1,j)){
                chmin(dp[i][j],dp[i][k]+dp[k][j]+as[j]-as[i]);
            }
        }
    }
    cout<<dp[0][N]<<endl;
    return 0;
}

Measured memory_bytes: 1536
#include<bits/stdc++.h>
using namespace std;   //author: madmin2619/mintu_agarwal
     
#define nfs() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long int
#define endl "\n"
#define pb push_back
#define pf push_front
#define forin(i, n) for(int i=0;i<n;i++)
#define tr(c, it) for(auto it=c.begin();it!=c.end();it++)
#define sz(c) c.size()
#define all(c) c.begin(),c.end()
#define ff first
#define ss second
#define m_p(x, y) make_pair(x, y)
     
const int M = 1e9 + 7;
const int N = 2e4+100;

bool comp(pair<int, pair<int, int> > a, pair<int, pair<int, int> > b){
	return (a.ff+ a.ss.ff) < (b.ff + b.ss.ff);
}

int32_t main(){
    nfs()
    int t, n, i, j, k;
    cin >> n;
    vector<pair<int, pair<int, int> > > v(n);
    forin(i, n)
    	cin >> v[i].ss.ff >> v[i].ff >> v[i].ss.ss;
    int dp[N];
    for(int i=0;i<N;i++)
    	dp[i]=0;
    sort(all(v), comp);
    for(int i=0;i<n;i++){
    	for(int j=v[i].ff;j>=0;j--){
    		dp[j+v[i].ss.ff]=max(dp[j+v[i].ss.ff], dp[j]+v[i].ss.ss);
    	}
    }
    int ans = 0;
    for(int i=0;i<N;i++)
    	ans = max(ans, dp[i]);
    cout << ans << '\n';
    return 0;
}

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

int main() {
  int a;
  int b;
  int k;
  int ans;
  int count=0;

  cin >> a >> b >> k;
  int c[100];

  for(int i=1;i<=100;i++){
    if(a%i==0 & b%i==0){
      c[count]=i;
      count++;
    }
  }
  count--;

  cout << c[count-(k-1)] << endl;

  return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;


class Program
{
    static void Main(string[] args)
    {
        int N = int.Parse(Console.ReadLine());
        //int N = 200000;

        var votes = new Dictionary<string, int>();
        int max = 0;
        for (int i = 0; i < N; i++)
        {
            string s = Console.ReadLine();
            //string s = i.ToString();

            int count = 1;
            if (votes.ContainsKey(s)) count = votes[s] + 1;
            votes[s] = count;

            max = Math.Max(count, max);
        }

        List<string> winners = new List<string>();
        foreach (var kvp in votes)
        {
            if (kvp.Value == max) winners.Add(kvp.Key);
        }
        string[] winnersArray = winners.ToArray();

        Array.Sort(winnersArray, new StringComparator());
        for (int i = 0; i < winnersArray.Length; i++) Console.WriteLine(winnersArray[i]);
        Console.ReadLine();       
    }

}

class StringComparator : IComparer<string>
{
    int IComparer<string>.Compare(string a, string b)
    {
        int length = Math.Min(a.Length, b.Length);
        //Console.WriteLine("Comparing with length {0}", length);
        for (int i = 0; i < length; i++)
        {
            if (a[i] < b[i])
            {
                //Console.WriteLine("returning -1");
                return -1;
            }
            else if (a[i] > b[i]) return 1;
        }
        if (a.Length < b.Length) return -1;
        if (a.Length > b.Length) return 1;

        //Console.WriteLine("Why are we at the end?");
        return 0;
    }
}



Measured memory_bytes: 40176
#include<iostream>
#include<algorithm>
#include<math.h>
#include<queue>
#include<vector>
#include<climits>
#include<map>
#include<string>
#include<functional>
#include<iomanip>
#include<deque>
#include<random>
#include<set>

using namespace std;
typedef long long ll;
typedef double lldo;
#define mp make_pair
#define pub push_back
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
ll gcd(ll a, ll b) { if (a % b == 0) { return b; } else  return gcd(b, a % b); }
ll lcm(ll a, ll b) { if (a == 0) { return b; }return a / gcd(a, b) * b; }
template<class T>ll LBI(vector<T>& ar, T in) { return lower_bound(ar.begin(), ar.end(), in) - ar.begin(); }
template<class T>ll UBI(vector<T>& ar, T in) { return upper_bound(ar.begin(), ar.end(), in) - ar.begin(); }

ll n, k, r, s, p, ans = 0;
bool memo[100000] = {};
string t;

int main() {
	cin >> n >> k >> r >> s >> p >> t;
	rep(i, n) {
		if ((i >= k && t[i] != t[i - k]) || i < k) {
			if (t[i] == 'r')ans += p;
			if (t[i] == 's')ans += r;
			if (t[i] == 'p')ans += s;
		}
		else {
			if (memo[i - k]) {
				if (t[i] == 'r')ans += p;
				if (t[i] == 's')ans += r;
				if (t[i] == 'p')ans += s;
				memo[i] = false;
			}
			else {
				memo[i] = true;
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 512
#include <algorithm>
#include <cmath>
#include <vector>
#include <functional>
#include <cstdlib>
#include <map>
#include <set>
#include <iostream>
#include <string>
#include <ctype.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < (int)(n); i++)



int main(){
	int n,d;
	cin >> n >> d;
	vector<vector<int>> x(n);
	int input;
	
	REP(i,n){
		REP(j,d){
			cin >> input;
			x[i].push_back(input);
		}
	}
	
	int ans=0;
	int kyo;
	double hikaku;
	
	REP(i,n){
		for(int j=i+1; j<n; j++){
			kyo=0;
			REP(k,d){
				kyo += (x[i][k]-x[j][k])*(x[i][k]-x[j][k]);
			}
			hikaku = sqrt(kyo);
			kyo = (int)hikaku;
			if(hikaku - kyo <= 1e-7) ans++; 
		}	
	}
	
	std::cout << ans << endl;
	
	
	
	
	
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, a, n) for (int i = (a); i < (int)(n); ++i)
#define REPC(i, a, n) for (int i = (a); i <= (int)(n); ++i)
#define ALL(t) t.begin(), t.end()
#define RALL(t) t.rbegin(), t.rend()
#define MATINIT(type, row, col, init) \
  vector<vector<type>>(row, vector<type>(col, init));
#define Yes(cond) cout << (cond ? "Yes" : "No") << endl;
#define YES(cond) cout << (cond ? "YES" : "NO") << endl;
using namespace std;
using LL = long long;
using ULL = unsigned long long;
template <class T>
using VEC = std::vector<T>;
template <class T>
using MAT = std::vector<std::vector<T>>;
void DUMP() { cerr << endl; }
template <class Head, class... Tail>
void DUMP(Head &&head, Tail &&... tail) {
  cerr << head << ", ";
  DUMP(std::move(tail)...);
}
template <typename T>
ostream &operator<<(ostream &os, vector<T> &vec) {
  os << "{";
  for (auto v : vec) os << v << ",";
  os << "}";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, map<T1, T2> &m) {
  os << "{";
  for (auto p : m) os << p << ",";
  os << "}";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, pair<T1, T2> p) {
  os << "[" << p.first << " " << p.second << "]";
  return os;
}

int main() {
  int H, W;
  cin >> H >> W;
  VEC<string> s(H);
  REP(i, 0, H) cin >> s[i];
  int black = 0, white = 0;
  REP(i, 0, H) {
    REP(j, 0, W) {
      if (s[i][j] == '#')
        ++black;
      else
        ++white;
    }
  }
  queue<pair<int, int>> q;
  queue<int> dist;
  bool queued[H][W];
  REP(i,0,H)REP(j,0,W)queued[i][j]=0;
  if (s[0][0] != '#') {
    q.push({0, 0});
    queued[0][0]=1;
  }
  dist.push(1);
  bool find = 0;
  while (!q.empty()) {
    auto p = q.front();
    int h = p.first;
    int w = p.second;
    if (h == H - 1 && w == W - 1) {
      find = 1;
      break;
    }
    int d = dist.front();

    if (h + 1 < H && s[h + 1][w] != '#' && !queued[h+1][w]) {
      q.push({h + 1, w});
      dist.push(d + 1);
      queued[h+1][w]=1;
    }
    if (h - 1 >= 0 && s[h - 1][w] != '#' && !queued[h-1][w]) {
      q.push({h - 1, w});
      dist.push(d + 1);
      queued[h-1][w]=1;
    }
    if (w + 1 < W && s[h][w + 1] != '#'&& !queued[h][w+1]) {
      q.push({h, w + 1});
      dist.push(d + 1);
      queued[h][w+1]=1;
    }
    if (w - 1 >= 0 && s[h][w - 1] != '#'&& !queued[h][w-1]) {
      q.push({h, w - 1});
      dist.push(d + 1);
      queued[h][w-1]=1;
    }
    q.pop();
    dist.pop();
  }
  if (find) {
    int path = dist.front();
    DUMP(black, white, path);
    cout << white - path << endl;
  } else
    cout << -1 << endl;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
#define ALL(x) (x).begin(), (x).end()
#define REP(i ,n) for(int i = 0; i < (int)(n); i++)
#define pb push_back
typedef vector<int>vint;
typedef vector<ll>vll;
template<typename T> istream &operator>>(istream &is, vector<T> &vec){ for (auto &v : vec) is >> v; return is; }
template<typename A,typename B>inline bool chmin(A &a,const B &b){if(a>b){a=b;return true;}else{return false;}}
template<typename A,typename B>inline bool chmax(A &a,const B &b){if(a<b){a=b;return true;}else{return false;}}

int main()
{
    string S;
    cin >> S;
    deque<char> ans;
    for(auto s:S){
        if(s == 'B' && ans.empty())continue;
        if(s == 'B' && !ans.empty()){
            ans.pop_back();
        }else{
            ans.push_back(s);
        }
    }

    while(!ans.empty()){
        cout << ans.front();
        ans.pop_front();
    }
    cout << endl;
}

Measured memory_bytes: 3596
#include<cstdio>
#include<cmath>
#include<string>
#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
#include<map>
#include<set>
#include<limits>
#include<bitset>
#include<array>
#include<numeric>
#include<iomanip>
#include<functional>
#include<deque>

using namespace std;
typedef long long int ll;

#define C cout<<
#define E <<endl

ll n,m,a,b,c,x,y,z,aa[200010],ab[200010],ac[1010][1010];
bool r,ra,rb,rc;
string s,sa,sb,sc;
char ca,cb,cc,cd[1010][1010];
vector<ll> va,vb,vc;

int main(){
    cin>>a;
    x=0;
    for(int i=1;i<=a;i++)x+=i;
    C x E;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int a[maxn];


int main()
{
    int n, k, i, j;
    cin>>n>>k;
    for(i=1; i<=n; i++)scanf("%d", &a[i]);
    for(i=1; i<=n; i++)
    {
        if(a[i]==k)return 0*printf("POSSIBLE\n");
    }
    sort(a+1, a+n+1);
    int q=1e9+7, ans=1;
    for(i=2; i<=n; i++)if(a[i]-a[i-1])q=min(q, a[i]-a[i-1]);
    if(q==(1e9+7))
    {
        if(a[1]==k)printf("POSSIBLE\n");
        else printf("IMPOSSIBLE\n");
        return 0;
    }

    for(i=2; i<=n; i++)if(a[i]-a[i-1])ans&=((a[i]-a[i-1])%q==0);
    int tmp=k;
    if(ans)
    {
        if(k%q==0 && k<=a[n])return 0*printf("POSSIBLE\n");
        else return 0*printf("IMPOSSIBLE\n");
    }

    if(k<=a[n])printf("POSSIBLE\n");
    else printf("IMPOSSIBLE\n");

    
    
}


Measured memory_bytes: 640
fun main(args: Array<String>) {
    val k = readLine()!!.toLong()

    if (k % 2 == 0L) return println(-1)

    var rem = 0L
    var digit = 1L
    var answer = 0L

    repeat(k.toInt()) {
        rem += digit * 7
        rem %= k
        answer++
        if (rem == 0L) return println(answer)
        digit *= 10
        digit %= k
    }

    println(-1)
}


Measured memory_bytes: 34480
#include<iostream>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
int dp[3005][3005];
int main()
{
    string a,b;
    cin>>a>>b;
    int x,y,i,j;
    x=a.length();
    y=b.length();
    for(i=x-1;i>=0;i--)
    {
    	for(j=y-1;j>=0;j--)
    	{
    		if(a[i]==b[j])
    		dp[i][j]=dp[i+1][j+1]+1;
    		else
    		dp[i][j]=max(dp[i+1][j],dp[i][j+1]);
		}
	}
	i=0;
	j=0;
	while(i<x&&j<y)
	{
		if(a[i]==b[j])
		{
			cout<<a[i];
			i++;
			j++;
		}
		else if(dp[i][j]==dp[i+1][j])
		i++;
		else j++;
	}
	return 0;
}

Measured memory_bytes: 38840
import sys
input=sys.stdin.buffer.readline
inputs=sys.stdin.buffer.readlines
sys.setrecursionlimit(10**9)
h,w,d=map(int,input().split())
inds={}
for i in range(h):
    for D,j in enumerate(input().split()):
        inds[int(j)-1]=(i,D)
nows=[[0]for c in range(d)]

for k in range(d,h*w):
    a,b=inds[k]
    x,y=inds[k-d]
    k%=d
    nows[k].append(nows[k][-1]+abs(a-x)+abs(b-y))
q=input()
for i in inputs():
    l,r=map(int,i.split())
    l-=1;r-=1
    l,b=divmod(l,d)
    r,b=divmod(r,d)
    print(nows[b][r]-nows[b][l])


Measured memory_bytes: 36940
#include<stdio.h>
int main(void)
{
   int H[300],W[300],i,j,k,flag=1,cnt=0;
   do{
      scanf("%d %d",&H[cnt],&W[cnt]);
      if(H[cnt]==0&&W[cnt]==0){
         flag=0;
      }
      cnt++;
   }while(flag);
   for(i=0;i<cnt-1;i++){
      for(j=0;j<H[i];j++){
         for(k=0;k<W[i];k++){
            if(j==0||j==H[i]-1){
               printf("#");
            }
            else if(k==0||k==W[i]-1){
               printf("#");
            }
            else{
               printf(".");
            }
         }
         printf("\n");
      }
      printf("\n");
   }
   return 0;
}

Measured memory_bytes: 572
N = int(input())

L = [i for i in range(10**5+1)]

for i in range(len(L)):
    for j in range(1,7):
        try: L[i + 6**j] = min(L[i + 6**j],L[i]+1)
        except: pass
    for j in range(1,6):
        try: L[i + 9**j] = min(L[i + 9**j],L[i]+1)
        except: pass
    try: L[i+1] = min(L[i+1],L[i]+1)
    except: pass
print(L[N])

Measured memory_bytes: 45040
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(x) (x).begin(),(x).end()
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(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;cin>>n;
    vector<ll> a(n);
    ll sum = 0;
    ll mcnt = 0;
    rep(i,n){
        ll t; cin>>t;
        if(t<0) {
            t = -t;
            mcnt++;
        }
        sum += t;
        a[i] = t;
    }
    sort(all(a));
    ll ans = mcnt%2==0 ? sum : sum-2*a[0];
    cout<< ans <<endl;
}

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

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define  inc(i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define  dec(i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))

#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define PQ priority_queue

#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
#define  FOR(it, v) for(auto it =  v.begin(); it !=  v.end(); ++it)
#define RFOR(it, v) for(auto it = v.rbegin(); it != v.rend(); ++it)

template<typename T> bool   setmin(T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool   setmax(T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

int a, b;

int main() {
	cin >> a >> b;
	
	inc(i, to_string(b).size()) { a *= 10; }
	a += b;
	
	bool f = false;
	incII(i, 0, a) {
		if(i * i == a) { f = true; }
	}
	
	cout << (f ? "Yes" : "No") << endl;
	
	return 0;
}


Measured memory_bytes: 256
//mo algo (no square root decomposition)
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define ff first
#define ss second
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<db, db> pdd;
typedef vector<int> vi;
#define m1 make_pair
#define in insert
#define pb push_back
#define int long long int
#define IOS                           \
    std::ios::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
#define endl "\n"
inline ll gcd(ll a, ll b)
{
    if (a == 0)
        return b;
    return gcd(b % a, a);
}
inline ll power(ll a, ll n, ll m)
{
    if (n == 0)
        return 1;
    ll p = power(a, n / 2, m);
    p = (p * p) % m;
    if (n % 2)
        return (p * a) % m;
    else
        return p;
}
const ll MOD = 998244353;
#define int long long int

int32_t main()
{
    IOS;
    string s;
    cin >> s;
    int n = s.size();
    int y = 0;
    for (int i = 0; i < n; i++)
        if (s[i] == 'o')
            y++;
    n = 15 - n;
    if (n + y >= 8)
    {
        cout << "YES";
    }
    else
    {
        cout << "NO";
    }
}

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

int main(void) {
    string s;
    cin >> s;
    int prev = s.at(0) - '0';
    int ans = 0;
    for (int i = 1; i < (int)s.size(); i++) {
        int n = s.at(i) - '0';
        if (n == prev) {
            n = 1 - prev;
            s.at(i) = (char)n;
            ans++;
        }
        prev = n;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3744
#include<bits/stdc++.h>
using namespace std;
int gcd(int m,int n){if(m%n==0)return n;else return gcd(n,m%n);}
int num(int a,int b,int c)
{
	if(a==b&&b==c)return 1;
	else if(a==b||b==c||c==a)return 3;
	else return 6;
}
int main()
{
	int n;cin>>n;
	char s[4444];cin>>s;
	long nr=0,ng=0,nb=0;
	for(int i=0;i<n;i++)nr+=s[i]=='R',ng+=s[i]=='G',nb+=s[i]=='B';
	long ans=nr*ng*nb;
	for(int i=0;i<n;i++)for(int d=1;i+d+d<n;d++)if((s[i]^s[i+d]^s[i+d+d])==('R'^'G'^'B'))ans--;
	cout<<ans<<'\n';
}

Measured memory_bytes: 3636
using System;
using System.Collections.Generic;
using System.Linq;

namespace test1
{
    class Program
    {
        static void Main(string[] args)
        {
            var line = default(string);
            line = Console.ReadLine();
            var parts = line.Split(' ');
            var H = int.Parse(parts[0]);
            var W = int.Parse(parts[1]);
            var K = int.Parse(parts[2]);

            var src = new bool[W, H];
            for (int h = 0; h < H; h++)
            {
                line = Console.ReadLine();
                for (int w = 0; w < W; w++)
                {
                    src[w,h] = line[w] == '#';
                }
            }

            int count = 0;
            int wpmax = 1 << W;
            int hpmax = 1 << H;
            for (int wp = 0; wp < wpmax; wp++)
            {
                for (int hp = 0; hp < hpmax; hp++)
                {
                    var dst = Dup(src);
                    for (int w = 0; w < W; w++)
                    {
                        if ((wp & (1 << w)) != 0)
                        {
                            PaintW(dst, w);
                        }
                    }
                    for (int h = 0; h < H; h++)
                    {
                        if ((hp & (1 << h)) != 0)
                        {
                            PaintH(dst, h);
                        }
                    }
                    if (CountBlack(dst) == K)
                    {
                        count++;
                    }
                }
            }

            Console.WriteLine(count);
            return;
        }

        private static void PaintW(bool[,] mat, int w)
        {
            for (int h = 0; h < mat.GetLength(1); h++)
            {
                mat[w, h] = false;
            }
            return;
        }

        private static void PaintH(bool[,] mat, int h)
        {
            for (int w = 0; w < mat.GetLength(0); w++)
            {
                mat[w, h] = false;
            }
            return;
        }

        private static bool[,] Dup(bool[,] src)
        {
            int W = src.GetLength(0);
            int H = src.GetLength(1);
            var dst = new bool[W, H];
            for (int w = 0; w < W; w++)
            {
                for (int h = 0; h < H; h++)
                {
                    dst[w, h] = src[w, h];
                }
            }
            return dst;
        }

        private static int CountBlack(bool[,] mat)
        {
            int W = mat.GetLength(0);
            int H = mat.GetLength(1);
            int n = 0;
            for (int w = 0; w < W; w++)
            {
                for (int h = 0; h < H; h++)
                {
                    if (mat[w, h])
                    {
                        n++;
                    }
                }
            }
            return n;
        }
    }
}


Measured memory_bytes: 27748
#include<stdio.h>
#include<stdlib.h>

int main(void){
  int n,i;
  char s[15],t[15];
  
  scanf("%s",s);
  scanf("%s",t);
  for(n=0;s[n]!='\0';n++){
  }
  for(i=0;i<n;i++){
    if(s[i]!=t[i]){
      printf("No");
      return 0;
    }
  }
    printf("Yes");
  
 return 0;
  
}
  
  

Measured memory_bytes: 1736
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
template <class T> void chmin(T& x, T y) { if (x > y) x = y; }
int main() {
    int N; cin >> N;
    vector<int> A(N), B(N);
    for (int i = 0; i < N; i++) cin >> A[i] >> B[i];
    Int ans = 1e18;
    chmin(ans, accumulate(begin(A), end(A), 0LL));
    chmin(ans, accumulate(begin(B), end(B), 0LL));
    vector<tuple<int, int, int>> C;
    for (int i = 0; i < N; i++) {
        C.emplace_back(A[i], i, 0);
        C.emplace_back(B[i], i, 1);
    }
    sort(begin(C), end(C));
    vector<int> used(N);
    Int sum = 0;
    bool ok = false;
    for (int i = 0; i < N; i++) {
        int val, idx, t;
        tie(val, idx, t) = C[i];
        sum += val;
        used[idx] |= 1 << t;
    }
    for (int u : used) if (u == 3) ok = true;
    if (ok) {
        chmin(ans, sum);
    } else {
        for (int i = 0; i < N; i++) {
            int last = get<0>(C[N-1]);
            if (get<1>(C[N-1]) == i) {
                last = get<0>(C[N-2]);
            }
            if (used[i] == 1) {
                chmin(ans, sum + B[i] - last);
            } else {
                chmin(ans, sum + A[i] - last);
            }
        }
    }
    cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 5620
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader breader = getReader();
		int n = getInt(breader); 
		String[] num = getAry(breader);
		int c = cardComp(num[0],num[1]);
		boolean stable = true;
		//duplicate ary
		String[] numbk = new String[n];
		for( int i = 0 ; i < n ; i++ ) {
			numbk[i] = num[i];
		}
		//initialize number array
		int[] nary = new int[n];
		for( int i = 0 ; i < n ; i++ ) {
			nary[i] = i;
		}
		//Bubble sort
		for( int i = 0 ; i < n ; i++ ) {
			for( int j = n-1 ; j > 0 ; j-- ) {
				if ( cardComp(num[j-1], num[j])> 0) {
					String wk = num[j-1];
					num[j-1] = num[j];
					num[j] = wk;
					int nwk = nary[j-1];
					nary[j-1] = nary[j];
					nary[j] = nwk;
				}
			}
		}
		stable = true;
		for( int i = 0 ; i < n-1 ; i++ ) {
			if ( cardComp(num[i], num[i+1]) == 0) {
				if ( nary[i] > nary[i+1] ) {
					stable = false;
					break;
				}
			}
		}
		putAry(num);
		if ( stable == true ) {
			System.out.println( "Stable");
		} else {
			System.out.println("Not stable");
		}
		//Selection sort
		//restore ary
		for( int i = 0 ; i < n ; i++ ) {
			num[i] = numbk[i];
			nary[i] = i;
		}
		for( int i = 0 ; i < n ; i++ ) {
			int mini = i;
			for( int j = i+1 ; j < n ; j++ ) {
				if ( cardComp(num[mini], num[j])> 0) {
					mini = j;
				}
			}
			String wk = num[i];
			num[i] = num[mini];
			num[mini] = wk;
			int nwk = nary[i];
			nary[i] = nary[mini];
			nary[mini] = nwk;
		}
		stable = true;
		for( int i = 0 ; i < n-1 ; i++ ) {
			if ( cardComp(num[i], num[i+1]) == 0) {
				if ( nary[i] > nary[i+1] ) {
					stable = false;
					break;
				}
			}
		}
		putAry(num);
		if ( stable == true ) {
			System.out.println( "Stable");
		} else {
			System.out.println("Not stable");
		}
	}
	public static BufferedReader getReader() {
		return( new BufferedReader(new InputStreamReader(System.in)));
	}
	public static int getInt(BufferedReader br)throws Exception {
		String line = br.readLine();
		return Integer.valueOf(line);
	}
	public static String[] getAry(BufferedReader br)throws Exception {
		String line = br.readLine();
		String[] nstr = line.split(" ");
		return nstr;
	}
	public static int cardComp(String left, String right) {
		char l = left.charAt(1);
		char r = right.charAt(1);
		return(l-r);
	}
	public static int[] getAryMl(BufferedReader br)throws Exception {
		int n = getInt(br);
		int[] ary = new int[n];
		for( int i=0 ; i < n ; i++ ) {
			ary[i] = getInt(br);
		}
		return ary;
	}
	public static void putAry(Object[] ary, int num) {
		for( int i = 0; i < num ; i++ ) {
			System.out.print(ary[i]);
			if ( i < num-1) {
				System.out.print(" ");
			}
		}
		System.out.println("");
	}
	public static void putAry(Object[] ary) {
		putAry(ary, ary.length ) ;
	}
	public static boolean isPrime(int n) {
		int r = (int)Math.sqrt((double)n)+1;
		for( int j = 2 ; j < r ; j += 1) {
			if ( n%j == 0 ) {
				return false;
			}
		}
		return true;
	}

	

}

Measured memory_bytes: 16976
import bisect

N = int(input())

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

ans = 0
mem_idx_a = {}
for idx_b in range(N):
  idx_c = bisect.bisect_right(C,B[idx_b])
  idx_a = bisect.bisect_left(A,B[idx_b])
  ans += (N-idx_c)*idx_a
print(ans)

Measured memory_bytes: 105444
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
#include<climits>
#define ll long long
using namespace std;

int main() {
	ll n, m,j=0;
	cin >> n >> m;
	queue<ll>a;
	vector<ll>dp(n+1,0);
	for (ll i = 0; i < m; i++) {
		ll s;
		cin >> s;
		if (m >= 2 && i >= 1 && s - a.front() == 1) {
			cout << "0" << endl;
			exit(0);
		}
		a.push(s);
		
	}
	a.push(LLONG_MAX);
	dp[0] = 1;
	dp[1] = 1;
	if (a.front() == 1) {
		dp[1] = 0;
		a.pop();
	}
	//cout << "0" << " " << dp[0] << endl;
	//cout << "1" << " " << dp[1] << endl;

	for (ll i = 2; i < n + 1; i++) {
		if (i != a.front()) {
			//cout << dp[i - 2] << endl;
			//cout << dp[i - 1] << endl;
			dp[i] =(dp[i - 1]+ dp[i - 2])%1000000007;
			//cout << i<<" "<<dp[i] << endl;
		}
		else {
			//cout << i << " " << dp[i] << endl;
			a.pop();
		}
		
		
	}
	cout << dp[n]%1000000007 << endl;

	
}

Measured memory_bytes: 1408
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	string s;

  	cin >> s;
  	
	long long n = s.size(), ans = 0;
	long long pcnt = 0, mcnt = 0, p = 0;
	for(long long i=0;i<n;i++){
		if(i<n-1&&s[i] == '<'){
			if(mcnt == 0){
				pcnt++;
			}else{
				ans += mcnt*(mcnt+1)/2;
				if(p>mcnt) ans += (p - mcnt);
				pcnt = 1;
				mcnt = 0;
				p = 0;
			}
		}else if(i<n-1&&s[i] == '>'){
			if(pcnt == 0){
				mcnt++;
			}else{
				ans += (pcnt-1)*pcnt/2;
				p = pcnt;
				pcnt = 0;
				mcnt++;
			}
		}else if(i == n-1&&s[i] == '<'){
			if(mcnt == 0){
				pcnt++;
				ans += pcnt*(pcnt+1)/2;
			}else{
				ans += mcnt*(mcnt+1)/2;
				if(p > mcnt) ans += (p - mcnt);
				ans++;
			}
		}else{
			if(pcnt == 0){
				mcnt++;
				ans += mcnt*(mcnt+1)/2;
			}else{
				ans += pcnt*(pcnt+1)/2;
			}
		}
	}
	
	cout << ans <<endl;
}



Measured memory_bytes: 900