akhauriyash/Code-Regression huggingface dataset:
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(v) v.begin(), v.end()
typedef long long 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 (b<a) { a=b; return 1; } return 0; }

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


int isPrime(int x){
  if(x<2) return 0;
  else if(x==2) return 1;
  if(x%2==0) return 0;
  for(int i=3;i*i<=x;i+=2){
    if(x%i==0) return 0;
  }
  return 1;
}

int main() {
  int x;
  cin>>x;
  
  while(1){
    if(isPrime(x)){
      cout<<x<<endl;
      return 0;
    }
    x++;
  }
    
  return 0;
}

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

using namespace std;

typedef long long ll;

int main(){
	int d,g;
	cin >> d >> g;g/=100;
	int point[d+1][2];
	int av[d+1];
	for(int i = 1; i <= d; i++){
		cin >> point[i][0] >> point[i][1];point[i][1]/=100;
	}
	int dp[d+1][g+200];
	fill(dp[0],dp[d+1],INF);
	dp[0][0]=0;
	for(int i = 1; i <= d; i++){
		for(int j = 0; j <= g+100; j++){
			for(int k = 0; k <= point[i][0]; k++){
				if(j-k*i<0)break;
				dp[i][j]=min(dp[i-1][j-k*i]+k,dp[i][j]);
			}
			dp[i][j]=min(dp[i-1][max(j-point[i][0]*i-point[i][1],0)]+point[i][0],dp[i][j]);
		}
	}
	/*for(int i = 0; i <= d; i++){
		for(int j = 0; j <= g+20; j++)cout << dp[i][j] << ' ';
		cout << endl;
	}*/
	cout << dp[d][g] << endl;
    return 0;
}

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

using namespace std;

typedef unsigned long long ull;
typedef long long ll;

int main(){
	ll h, s=0;
	int n;
	cin >> h >> n;
	for(int i=0; i<n; i++){
		int a;
		cin >> a;
		s+=a;
	}
	if(s>=h) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h> 
using namespace std; 
#define int long long
# define pii pair<int,int>
const int maxn=1e6+5;
signed main() { 
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin>>n;
    vector<int> arr(n),num(1000100),div(1000100);
    for(int i=0;i<n;i++)
    {
    	cin>>arr[i];
    	num[arr[i]]++;
    }
    for(int i=1;i<=1000000;i++)
    {
    	for(int j=i;j<=1000000;j+=i)
    		div[j]+=num[i];
    }
    int ans=0;
    for(int i=0;i<n;i++)
    {
    	if(div[arr[i]]==1)ans++;
    }
    cout<<ans;
}

Measured memory_bytes: 20364
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair<int, int>;
using VI = vector<int>;

int main() {
#ifdef LOCAL_EXEC
//	freopen("sample.in", "r", stdin);
//	freopen("sample.out", "w", stdout);
#else
  ios_base::sync_with_stdio(false); cin.tie(NULL);
#endif

  string s; cin >> s;
  if (s[2] == s[3] && s[4] == s[5]) cout << "Yes\n";
  else cout << "No\n";

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
using ll = long long;
using pii = pair<int,int>;
using vi = vector<int>;
using vs = vector<string>;
using vll = vector<long long>;
using vpii = vector<pair<int,int>>;
using vivi = vector<vector<int>>;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};



int main(void) {
  int k,x;
  cin >> k >> x;
  rep2(i,max(x-k+1,-1000000),min(x+k,1000001))cout << i << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxx = 300;
int a[300];
int n;
int ans=0;
int main(){	
	cin>>n;
	for(int i=1;i<=2*n;i++)cin>>a[i];
	sort(a+1,a+2*n+1);
	for(int i=1;i<=2*n;i+=2)ans+=a[i];
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<math.h>
#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<set>
typedef long long ll;
using namespace std;

int main(void) {
	ll n, m, ans = 0;
	cin >> n >> m;
	if (n == m) {
		if (n == 1) {
			cout << ans << endl;
		}
		else {
			while (m >= 2) {
				ans++;
				m -= 2;
			}
			cout << ans << endl;
		}
	}
	else {
		if (n > m) {
			if (m == 1) {
				cout << ans << endl;
			}
			else {
				while (m >= 2) {
					ans++;
					m -= 2;
				}
				cout << ans << endl;
			}
		}
		else {
			while (true) {
				n--;
				m -= 2;
				ans++;
				if (m < 2) {
					cout << ans << endl;
					return 0;
				}
				if (n == 0)break;
			}
			while (m >= 4) {
				m -= 4;
				ans++;
			}
			cout << ans << endl;
		}
	}
	return 0;
}

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

public class Test
{
	public static void Main()
	{
		// your code goes here
		
		int n = int.Parse(Console.ReadLine());
		var a = Console.ReadLine().Split().Select(nyan => int.Parse(nyan)).ToArray(); //この呪文覚えたい
		int[] c = new int[n];
		int x = 0;
		for(int i=0; i!=n-1; i++){
			
			x = a[i];
			c[x-1] += 1;
			
		}
		for(int j=0; j!=n; j++){
			Console.WriteLine(c[j]);
		}
		
	}
}

Measured memory_bytes: 43856
s = input()
if ((s[0] == s[1] and s[0] != s[2] and s[2] == s[3])
  or (s[0] == s[2] and s[0] != s[1] and s[1] == s[3])
  or (s[0] == s[3] and s[0] != s[1] and s[1] == s[2])):
  print('Yes')
else:
  print('No')

Measured memory_bytes: 3060
#include <iostream>

int main()
{
    int c1, c5, c10, c50, c100, c500;
    std::cin >> c1 >> c5 >> c10 >> c50 >> c100 >> c500;
    if((c1 + c5 * 5 + c10 * 10 + c50 * 50 + c100 * 100 + c500 * 500) >= 1000)
        std::cout << 1 << std::endl;
    else
        std::cout << 0 << std::endl;
    return 0;
}

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

int main() {
	string s; cin >> s;
  	bool possible = true;
  	for (int i = 0; i < s.length(); i++) {
    	if (i & 1 and s[i] == 'R') {
        	possible = false;
          	break;
        } else if (i % 2 == 0 and s[i] == 'L') {
        	possible = false;
          	break;
        }
    }
  	if (possible) cout << "Yes\n";
  	else cout << "No\n";
}

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N;
		while ((N = Integer.parseInt(br.readLine())) > 0) {
			HashMap<Integer, Integer> lhm = new LinkedHashMap<>();
			
			for (int i = 0; i < N; i++) {
				String[] lc = br.readLine().split(" ");
				int a = Integer.parseInt(lc[0]);
				int b = Integer.parseInt(lc[1]);
				int c = Integer.parseInt(lc[2]);

				Integer cur = lhm.get(a);
				if(cur != null) {
					lhm.replace(a, cur + b*c);
				}
				else
				{
					lhm.put(a, b*c);
				}
			}
			
			boolean zzz = false;
			for (Integer key : lhm.keySet()){
				Integer cur = lhm.get(key);
				if(cur >= 1000000){
					System.out.println(key);
					zzz = true;
				}
			}
			
			if(!zzz)
				System.out.println("NA");
		}

	}
}

Measured memory_bytes: 25960
#include <algorithm>
#include <bitset>
#include <complex>
#include <cstdio>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif

using namespace std;

#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)

typedef long long ll;

const int Inf = 1e9;
const double EPS = 1e-9;

int gcd(int a, int b) {
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}

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

int bitCount(long bits) {
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
    return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n, m;  cin >> n >> m;
    if (n == 1 && m == 1) {
      cout << 1 << '\n';
    } else if (n == 1 && m > 1) {
      cout << m - 2 << '\n';
    } else if (n > 1 && m == 1) {
      cout << n - 2 << '\n';
    } else {
      cout << (n - 2) * (m - 2) << '\n';
    }

    return 0;
}


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

public class Main
{
    PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer tok;

    public void go() throws IOException
    {
        ntok();
        int n = ipar();
        ntok();
        int[] a = iapar(n);
        ntok();
        int[] b = iapar(n);
        ntok();
        int[] c = iapar(n-1);
        int sum = 0;
        for (int i = 0; i < n; i++)
        {
            sum += b[i];
        }
        for (int i = 0; i < n-1; i++)
        {
            if (a[i+1] == a[i]+1)
            {
                sum += c[a[i]-1];
            }
        }
        out.println(sum);

        out.flush();
        in.close();
    }

    public void ntok() throws IOException
    {
        tok = new StringTokenizer(in.readLine());
    }

    public int ipar()
    {
        return Integer.parseInt(tok.nextToken());
    }

    public int[] iapar(int n)
    {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
        {
            arr[i] = ipar();
        }
        return arr;
    }

    public long lpar()
    {
        return Long.parseLong(tok.nextToken());
    }

    public long[] lapar(int n)
    {
        long[] arr = new long[n];
        for (int i = 0; i < n; i++)
        {
            arr[i] = lpar();
        }
        return arr;
    }

    public double dpar()
    {
        return Double.parseDouble(tok.nextToken());
    }

    public String spar()
    {
        return tok.nextToken();
    }

    public static void main(String[] args) throws IOException
    {
        new Main().go();
    }
}


Measured memory_bytes: 21844
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

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

            int keta = (int)Math.Floor(Math.Log10(N)) + 1;

            //int keta = 2;
            string output = "";
            int remain;

            var outPutList = new List<string>();

            for (int k = keta; k >= 1; k--) {
                for (int i = 0; i < (int)Math.Pow(3, k); i++) {
                    output = "";
                    int temp = i;

                    for (int pos = 0; pos < k; pos++) {
                        remain = temp % 3;

                        output = remain.ToString() + output;

                        temp /= 3;
                    }
                    outPutList.Add(output);
                }
            }


            //0, 1, 2の集合
            var neededList = new List<char> { '0', '1', '2' };

            //3, 5, 7の集合
            var shichigosanList = new List<char> { '3', '5', '7' };

            int ans = 0;

            for (int i = 0; i < outPutList.Count(); i++) {
                //3種類の文字がそろっていない場合は飛ばす
                if (outPutList[i].ToCharArray().ToList().Intersect(neededList).Count() != 3) {
                    continue;
                }

                //文字列から整数を生成
                string num_str = "";

                for (int j = 0; j < outPutList[i].Length; j++) {
                    num_str += shichigosanList[int.Parse(outPutList[i][j].ToString())].ToString();
                }
                int num = int.Parse(num_str);

                //Console.WriteLine(num);

                if (num <= N) {
                    ans++;
                    //Console.WriteLine("Counted!");
                    //Console.WriteLine(outPutArray[i]);
                }


            }


            Console.WriteLine(ans);

        }


    }
}


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

int main(){
    string s, t;
    cin >> s >> t;
    int c = 0;
    for (int i = 0; i < 3;i++)
    {
        if(s[i] == t[i])
            c++;
    }
    cout << c;
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
using namespace std;

int main()
{
  int z;
  while (scanf("%d", &z), z) {
    int m = -1;
    for (int x = 1; x < z; ++x) {
      int lo = 1, hi = z;
      while (lo < hi) {
        int y = (lo + hi + 1) / 2;
        if (x*x*x + y*y*y <= z*z*z)
          lo = y;
        else
          hi = y-1;
      }
      m = max(m, x*x*x + lo*lo*lo);
    }
    printf("%d\n", z*z*z - m);
  }
}

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

int main(){
    int n;
    scanf("%d", &n);
    int X[n], Y[n];
    REP(i, n){
        scanf("%d", &X[i]);
        Y[i] = X[i];
    }
    sort(Y, Y + n);

    REP(i, n){
        if(X[i] <= Y[n / 2 - 1]) printf("%d\n", Y[n / 2]);
        else printf("%d\n", Y[n / 2 - 1]);
    }
    
    return 0;
}


Measured memory_bytes: 3712
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author tatsumack
 */

#include <iostream>
#include <fstream>

#include <bits/stdc++.h>

#define int long long
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define FOR(i, a, b) for (int i = (a), i##_len = (b); i <= i##_len; ++i)
#define REV(i, a, b) for (int i = (a); i >= (b); --i)
#define CLR(a, b) memset((a), (b), sizeof(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define INF 1001001001001001001ll
#define fcout cout << fixed << setprecision(12)

using namespace std;

typedef pair<int, int> P;

class DAlterAltar {
public:
    void solve(std::istream& cin, std::ostream& cout) {
        int N;
        cin >> N;
        string s;
        cin >> s;

        int red = 0;
        for (auto c : s) {
            if (c == 'R') red++;
        }

        int white = 0;
        REP(i, red) {
            if (s[i] == 'W') white++;
        }
        cout << min(red, white) << endl;
    }
};


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    std::istream& in(std::cin);
    std::ostream& out(std::cout);

    DAlterAltar solver;
    solver.solve(in, out);
    return 0;
}


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

// clang-format off
#define IOS ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(NULL)
#define forn(i, x, y) for(int i = x; i < y; i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }

using ll = long long;
// clang-format on

int main()
{
  IOS;

  int N, W;
  cin >> N >> W;
  vector<int> w(N), v(N);
  forn(i, 0, N) cin >> w[i] >> v[i];

  vector<ll> dp(W + 1, 0);
  for (int i = 0; i < N; i++)
  {
    for (int j = W; j >= w[i]; j--)
    {
      chmax(dp[j], dp[j - w[i]] + v[i]);
    }
  }
  cout << dp[W] << endl;

  return 0;
}


Measured memory_bytes: 3948
N = int(input())
w = [int(x) for x in input().split()]

s1 = 0
s2 = sum(w)
tmp = s2 + 10

for i in range(N):
    s1 += w[i]
    s2 -= w[i]
    if tmp < abs(s2 - s1):
        break
    tmp = s2 - s1
print(min(abs(tmp), abs(s2-s1)))

Measured memory_bytes: 3064
#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
#include <map>
#include <set>
#include <string>
#include <iostream>
#include <cassert>
#include <cmath>
using namespace std;

int main() {
        int n;
        scanf("%d", &n);
        vector<int> cnt(6);
        for (int i = 0; i < n; i ++) {
                string s;
                cin >> s;
                if (s[0] == 'M') cnt[0] ++;
                if (s[0] == 'A') cnt[1] ++;
                if (s[0] == 'R') cnt[2] ++;
                if (s[0] == 'C') cnt[3] ++;
                if (s[0] == 'H') cnt[4] ++;
        }
        long long ans = 0;
        for (int i = 0; i < 5; i ++) {
                for (int j = i + 1; j < 5; j ++) {
                        for (int k = j + 1; k < 5; k ++) {
                                ans += (long long) cnt[i] * cnt[j] * cnt[k];
                        }
                }
        }
        printf("%lld\n", ans);
        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 REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size)
#define MOD 1000000007
const long long mod = 1e9+7;
typedef vector<long long> Vl;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<Vl> VVl;
typedef pair<int, int> PII;
typedef long long ll;

int main(){
    int a=0,b=0,c=0,d,n=0,x=0;
    VI m(3);
    string s,s1,s2;
    cin >> a >> b >>c; 
    if(a>=b && a>=c) {
        d += a*10;
        d += c+b;
    }
    else if(b>=c && b>=a) {
        d += b*10;
        d += c+a;
    }
    else {
        d += c*10;
        d += b+a;
    }
    cout << d <<endl;
    return 0;
} 

Measured memory_bytes: 256
#include <cstdio>
#include <cstdint>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <array>
#include <vector>
#include <unordered_map>
#include <unordered_set>

int main()
{
    std::string s;
    std::cin >> s;
    if (s[0] != 'A') {
        std::printf("WA\n");
        return 0;
    }

    int cnt = 0;
    for (std::size_t i = 2; i < s.size() - 1; ++i) {
        if (s[i] == 'C') {
            ++cnt;
        } else if (s[i] < 'a' || 'z' < s[i]) {
            std::printf("WA\n");
            return 0;
        }
    }

    if (cnt != 1) {
        std::printf("WA\n");
        return 0;
    }

    if (s[1] < 'a' || 'z' < s[1]) {
        std::printf("WA\n");
        return 0;
    } else if (s[s.size() -1] < 'a' || 'z' < s[s.size() -1]) {
        std::printf("WA\n");
        return 0;
    }

    std::printf("AC\n");

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
int main() {
 
   ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
   
 	  ll a,b,c;
 	  
 	  cin >> a >> b >> c;
 	  
 	  if(a!=b&&b==c){
 	  	cout << "Yes" << endl;
	   }else if(c!=a&&b==a){
	   	cout << "Yes" << endl;
	   }else if(b!=a&&a==c){
	   	cout << "Yes" << endl;
	   }else{
	   	cout << "No" << endl;
	   }
   
return 0;   
}


Measured memory_bytes: 3616
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> using vt = vector<T>;
template<class T> using vvt = vector<vt<T>>;
template<class T> using ttt = tuple<T,T>;
using tii = tuple<ll,ll>;
using vi = vector<ll>;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define pb push_back
#define mt make_tuple
#define ALL(a) (a).begin(),(a).end()
#define FST first
#define SEC second
#define DEB cerr<<"!"<<endl
#define SHOW(a,b) cerr<<(a)<<" "<<(b)<<endl
#define DIV int(1e9+7)
const int INF = (INT_MAX/2);
const ll LLINF = (LLONG_MAX/2);
const double eps = 1e-8;
const double PI = M_PI;  
inline ll pow(ll x,ll n,ll m){ll r=1;while(n>0){if((n&1)==1)r=r*x%m;x=x*x%m;n>>=1;}return r%m;}
inline ll lcm(ll d1, ll d2){return d1 / __gcd(d1, d2) * d2;}
 
/* Coding Space*/
typedef complex<double> P;
namespace std {
  bool operator < (const P& a, const P& b) {
    return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
  }
}
double cross(const P& a, const P& b) {
  return imag(conj(a)*b);
}
double dot(const P& a, const P& b) {
  return real(conj(a)*b);
}

struct L : public vector<P> {
  L(const P &a, const P &b) {
    push_back(a); push_back(b);
  }
};

typedef vector<P> G;

struct C {
  P p; double r;
};
C circles[1002];
double table[1002][1002] = {};

int main(){
  double xs,ys,xt,yt; cin >> xs >> ys >> xt >> yt;
  int n; cin >> n;
  circles[0] = C{P{xs,ys},0};
  circles[1] = C{P{xt,yt},0};
  for(int i = 2; i < n + 2;i++){
    double x,y,r; cin >> x >> y >> r;
    circles[i] = C{P{x,y},r};
  }
  rep(i,n+2)rep(j,n+2){
    if(i == j) table[i][j] = 0.;
    else{
      table[i][j] = max(0.,abs(circles[i].p - circles[j].p) - circles[i].r - circles[j].r);
      //cerr << i << " " << j << " " << table[i][j] << endl;
    }
  }
  using tdi = tuple<double,int>; // cost,index
  priority_queue<tdi,vt<tdi>,greater<tdi>> q;
  q.push(tdi{0.0,0});
  bool used[1002] = {};
  while(1){
    double cost; int index; tie(cost,index) = q.top(); q.pop();
    if(used[index]) continue;
    if(index == 1) {
      cout << fixed << setprecision(20) << cost << endl;
      return 0;
    }else{
      rep(i,n+2){
        if(i != index)
          q.push(tdi{table[index][i] + cost,i});
      }
    }
    used[index] = 1;
  }
}

Measured memory_bytes: 26472
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        n: usize,
        a: [[usize1; n - 1]; n],
    }
    let mut a = a;
    let mut pos = vec![0; n];
    for i in 0..n {
        a[i].push(n);
    }

    let mut ok: Vec<usize> = vec![];
    for i in 0..n {
        let j = a[i][0];
        if a[j][0] == i {
            ok.push(i);
            ok.push(j);
        }
    }

    let mut ans = 0;
    while !ok.is_empty() {
        let mut nxt = vec![];
        ans += 1;

        let set: std::collections::HashSet<_> = ok.drain(..).collect(); // dedup
        ok.extend(set.into_iter());
        for &i in ok.iter() {
            pos[i] += 1;
        }

        for &i in ok.iter() {
            if pos[i] >= n - 1 {
                continue;
            }
            let j = a[i][pos[i]];
            if a[j][pos[j]] == i {
                nxt.push(i);
                nxt.push(j);
            }
        }
        ok = nxt;
    }

    if pos.iter().any(|p| *p < n - 1) {
        ans = -1;
    }
    println!("{}", ans);
}


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

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef pair<ll, int> PILL;
typedef pair<ll, ll> PLL;

const int MAX_N = 1000111;
const ll INF = (ll)(1e18);
const ll MOD = 1000000007LL;

void solve() {

}

struct Edge {
    int u;
    int v;
    ll w;
};

int n, m;
ll p;
vector<Edge> edges;
ll dist[2505];

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

    cin >> n >> m >> p;
    for (int i=1; i<=n; i++) dist[i] = INF;
    dist[1] = 0LL;

    for (int i=0; i<m; i++) {
        int x, y; ll c;
        cin >> x >> y >> c;
        edges.push_back({x,y,-c+p});
    }

    bool negCycle = false;
    for (int i=0; i<2*n; i++) {
        for (int j=0; j<m; j++) {
            int u = edges[j].u;
            int v = edges[j].v;
            ll w = edges[j].w;
            if (dist[u] < INF) {
                if (dist[v] > dist[u]+w) {
                    dist[v] = dist[u]+w;
                    if (i >= n && v == n) {
                        negCycle = true;
                    }
                }
            }
        }
    }

    //cout << "D: " << negCycle << "\n";
    if (negCycle || dist[n]==INF) {
        cout << -1;
    } else {
        cout << max(0LL, -dist[n]);
    }


    return 0;
}


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

    int t,i,j,n,a,b;
    string s,s1;
    cin>>a>>b;
    if((a>=0&&a<=9)&&(b>=0&&b<=9))
    cout<<a*b<<"\n";
    else
        cout<<"-1"<<"\n";



return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	private static String halfSpace = " ";

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

		String tmp = scanner.nextLine();

		scanner.close();

		String[] tmpStrs = tmp.split(halfSpace);

		int a_button = Integer.parseInt(tmpStrs[0]);

		int b_button = Integer.parseInt(tmpStrs[1]);

		int count = 2;

		int max = 0;

		for(int i = 0; i < count; i++) {
			if(a_button > b_button) {
				max = max + a_button;
				a_button--;
			}else if(b_button > a_button) {
				max = max + b_button;
				b_button--;
			}else {
				max = max + a_button;
			}

		}

		System.out.println(max);
	}

}

Measured memory_bytes: 23892
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
#include <set>
#include <vector>
#include <map>
#include <list>
#include <stack>
#define REP(i, n) for(i=0; i<n; i++)
#define REPR(i, n) for(i=n; i>=0; i--)
#define FOR(i, m, n) for(i=m; i<n; i++)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> p;

ll memo[100001]={0};

ll rec(ll n);

int main(void) {
    ll a, b, k;
    set<ll> s;
    cin>>a>>b>>k;
    ll i;
    for(i=a; i<a+k&&i<b; i++)
        s.insert(i);
    
    for(i=max(b-k+1, a); i<=b; i++)
        s.insert(i);
    
    for(auto itr=s.begin(); itr!=s.end(); itr++)
        cout << *itr << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s,t;
    cin>>s>>t;
    long long int cnt=0;
    for(int i=0;i<(min(s.length(),t.length()));i++)
        if(s[i]!=t[i])
          cnt++;
          int m=s.length();
          int n=t.length();
    cnt+=abs(m-n);
    cout<<cnt<<endl;
    return 0;
}


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

typedef long long ll;

ll N, M;

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

    vector<ll> P(M), Y(M);
    rep(i, M) cin >> P[i] >> Y[i]; 

    map<ll, vector<pair<ll, ll>>> mp;
    rep(i, M) {
        mp[P[i]].push_back(make_pair(Y[i], i + 1)); 
    }

    map<ll, pair<ll, ll>> ans;

    // 県ごとに処理
    for (auto iter = mp.begin(); iter != mp.end(); iter++) {
        sort(iter->second.begin(), iter->second.end());

        for (ll i = 0; i < iter->second.size(); i++) {
           // printf("p: %06d f: %d s: %d idx: %06d\n", 
           // iter->first, iter->second[i].first, iter->second[i].second, i + 1);
           // ans[iter->second[i].second] = sprintf("%")  
           // cout << sprintf("%d", iter->second[i].second) << endl;
           ans[iter->second[i].second] = make_pair(iter->first, i + 1);
        }
    }

    for (auto iter = ans.begin(); iter != ans.end(); iter++) {
        printf("%06lld%06lld\n", ans[iter->first].first, ans[iter->first].second);
    }
}

Measured memory_bytes: 20224
process.stdin.resume();
process.stdin.setEncoding('utf8');

var g_input = '';
process.stdin.on('data', function(chunk) {
    g_input += chunk;
});

process.stdin.on('end', function() {
    Main(g_input.split(/\r?\n/));
});

function Main(input) {
    var capitalN = parseInt(input[0], 10);
    var h = 0;
    var n = 0;
    var w = 0;

    var a = 4 / capitalN;
    var b = 2 / 3500;
    var c = 1 / 3500;

    var isFound = false;
//    console.log(Math.floor(1 / (a - b)));
//    for (h = Math.floor(1 / (a - b)); h < 3500; h++) {
    for (h = 1; h <= 3500; h++) {

//        if (a < 1 / h + b) {
//            continue;
//        }

//        console.log(Math.floor(1 / (a - 1 / h - c)));
//        for (n = Math.floor(1 / (a - 1 / h - c)); n < 3500; n++) {
        for (n = h; n <= 3500; n++) {

//            if (a < 1 / h + 1 / n + c) {
//                continue;
//            }

            if (4 * h * n - capitalN * h - capitalN * n != 0) {
                w = Math.ceil((capitalN * h * n) / (4 * h * n - capitalN * h - capitalN * n));
            //for (w = n; w < 3500; w++) {

                if (w > 0 && a === 1 / h + 1 / n + 1 / w) {
                    isFound = true;
                    break;
                }
            //}
            }

            if (isFound) {
                break;
            }
        }

        if (isFound) {
            break;
        }
    }

    console.log(h + ' ' + n + ' ' + w);

    return 0;
}


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

int main() {
    int n; scanf("%d", &n);
    int a[n]; for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
    int num_query, k; scanf("%d", &num_query);
    
    for (int i = 0; i < num_query; ++i) {
        scanf("%d", &k);
        int result = lower_bound(a, a + n, k) - a;
        printf("%d\n", result);
    }
    return 0;
}


Measured memory_bytes: 3124
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;

int main(void){
    IOS;
    string s; cin >> s;
    if (s == "ABC") cout << "ARC" << endl;
    else cout << "ABC" << endl;
    return 0;
}

Measured memory_bytes: 3604
#include<bits/stdc++.h>
#define pb          push_back
#define endl        '\n'
#define pll         pair<int,int>
#define vll          vector<int>
#define all(a)      (a).begin(),(a).end()
#define x           first
#define y           second
#define hell        1000000007
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define gcd(a,b)    __gcd((a),(b))
#define lcm(a,b)    ((a)*(b)) / gcd((a),(b))
#define int	    int64_t
#define ios     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 
int n,i,j,k,l,sum=0,flag=0,t,a[101],m;
int dp[100001],dp2[100005];
int get(int l , int r){
	int ans= dp[r];
	if(l>0)
		ans-=dp[l-1];
	return (ans+hell)%hell;
}
void solve(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
    for(int i=0;i<=k;i++) dp[i]=1;
    for(int i=1;i<=n;i++){
    	for(int j=k;j>=0;j--){
    		dp2[j]=get(j-a[i],j);
    	}
    	for(int j=1;j<=k;j++){
    		dp[j] = dp[j-1]+dp2[j];
    	}
    }
    cout<<dp[k]-dp[k-1]<<endl;

}
signed main()
{
    ios
    int test = 1;
    //cin>>test;
    while(test--){
    	solve();
    }
    return 0;
}

Measured memory_bytes: 1792
import itertools
n, m, x = map(int, input().split())
a_list = []
for i in range(n):
	targets = list(map(int, input().split()))
	a_list.append(targets)
r_list = []
for i, _ in enumerate(a_list, 1):     
	for j in itertools.combinations(a_list, r=i):
		targets = [0] * (m+1)
		for t in j:
			k = 0
			for target in t:
				targets[k] += target
				k += 1
		pop_list = targets[1:m+1]
		if min(pop_list) >= x:
			r_list.append(targets)
if len(r_list) == 0:
	print(-1)
else:
	result = sorted(r_list, key=lambda x: x[0])
	print(result[0][0])

Measured memory_bytes: 68304
from collections import deque
import sys, copy, itertools,heapq
#input = sys.stdin.readline
 
S = input()
T = input()
s = len(S)
t = len(T)
A=[0]*(len(S))
 
ans = t
for i in range(len(S)-len(T)+1):
  for j in range(len(T)):
    if S[i+j] != T[j]:
      A[i] += 1
  ans = min(ans, A[i])
 
#print(s)
#print(t)
#print(ANS)
print(ans)

Measured memory_bytes: 9380
#include<bits/stdc++.h>
using namespace std;
int mincosttogo(int a[],int memo[],int st,int end,int k)
{
  if(st>=end)
    return 0;
  if(memo[end]!=-1)
    return memo[end];
  int temp1=INT_MAX,temp2=INT_MAX;
 // if(end>=1)
    for(int i=1;i<=k;i++)
    {
      if(end -i>=0)
      temp2=mincosttogo(a,memo,st,end-i,k)+abs(a[end]-a[end-i]);
      temp1=min(temp1,temp2);
    }
 
  return memo[end]=temp1;
}
int main()
{
  int n;
  cin >> n;
  int k;
  cin >> k;
  int a[n];
  for(int i=0;i<n;i++)
  cin >> a[i];
  int memo[n+1];
  for(int i=0;i<=n;i++)
    memo[i]=-1;
  cout << mincosttogo(a,memo,0,n-1,k) << endl;
  return 0;
}

Measured memory_bytes: 13732
import java.util.*;

public class Main {
	public static void main(String[] args) {
		 
            Scanner sc = new Scanner(System.in);
            
            long H = sc.nextLong();
            long W = sc.nextLong();         
            
            if(H%3 == 0 || W%3 == 0){
                System.out.println(0);
                return;
            }
            
            //1 H 
                        
            long h1 = H%3;
            long h3 = H%3 + 1;
            
            long min = calc(h1*W,h1*W,h3*W);
            
            long hh1 = H%3;
            long hh3 = H%3 + 2;
                        
            min = Math.min(min,calc(hh1*W,hh1*W,hh3*W));
            
            //2 W
            
            long w1 = W%3;
            long w3 = W%3 + 1;
            
            min = Math.min(min,calc(w1*H,w1*H,w3*H));
            
            long ww1 = W%3;
            long ww3 = W%3 + 2;
            
            min = Math.min(min,calc(ww1*H,ww1*H,ww3*H));
                                    
            // 3
                        
            long w = W/2;
            
            for(int h = 1;h <= H - 1;h++){
               long S1 = w*h;
               long S2 = (W-w)*h;
               long S3 = (H-h)*W;
               min = Math.min(min,calc(S1,S2,S3));
            }                
            
            // 4            
                  
            long h = H/2;
            
            for(int ww = 1;ww <= W - 1;ww++){
                long S1 = ww*h;
                long S2 = (H-h)*ww;
                long S3 = H*(W-ww);
                min = Math.min(min,calc(S1,S2,S3));
            }                            
            
            System.out.println(min);
            
        }
        
        public static long calc(long S1,long S2,long S3){
            long MAX = S1;                        
            
            MAX = Math.max(MAX,S2);            
            MAX = Math.max(MAX,S3);
            
            long MIN = S1;
            
            MIN = Math.min(MIN,S2);
            MIN = Math.min(MIN,S3);
           
            return MAX - MIN;            
        }
        
}

        
        
        
        
        
        
        
        
        
        
        

Measured memory_bytes: 22996
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <tuple>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cassert>
#include <cstdint>
#include <numeric>
#include <bitset>
#include <functional>

using namespace std;

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

constexpr ll MOD = 1000000007;
constexpr long double EPS = 1e-10;
constexpr int dyx[4][2] = {
    { 0, 1}, {-1, 0}, {0,-1}, {1, 0}
};

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    int a[n];
    for(int i=0;i<n;++i) {
        cin >> a[i];
    }

    int m = 1, ans = 0;
    for(int i=0;i<n;++i) {
        if(a[i] == m) {
            ++m;
        } else {
            ++ans;
        }
    }
    if(ans == n) ans = -1;
    cout << ans << endl;
}


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

int main(){
  int N,n,ket=1,z=1,ans=0;cin >> N;n=N;
  while(n>=10){
    n /= 10;
    ket++;
    z *= 10;
  }
  int mount=9;
  for (int i=0;i<ket;i+=2){
    ans += mount;
    mount *= 100;
  }
  int minus=9;
  for(int i=2;i<ket;i++){
    minus *= 10;minus += 9;
  }
  if (ket%2 != 0){
    ans -= mount/100;
    ans += N-minus;
  }
  if (N > 9){
  cout << ans <<endl;
}else{
  cout << N << endl;
}
}


Measured memory_bytes: 256
import itertools
inpl = lambda: list(map(int,input().split()))
H, W, K = inpl()
S = [input() for h in range(H)]
ans = H+W
for c in itertools.product(range(2),repeat=H-1):
    hcut = sum(c)
    if hcut >= ans:
        continue
    segment = [0]
    s = 0
    for h in range(H-1):
        if c[h]:
            s += 1
        segment.append(s)
    cur = hcut
    whites = [0] * (hcut+1)
    for w in range(W):
        thisline = [0]*(hcut+1)
        for h in range(H):
            if S[h][w] == '1':
                whites[segment[h]] += 1
                thisline[segment[h]] += 1
        m = max(whites)
        if m > K:
            whites = thisline
            m = max(whites)
            cur += 1
            if cur >= ans or m > K:
                break
    else:
        ans = cur
            
print(ans)

Measured memory_bytes: 47068
#include<iostream>
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<math.h>
#include<algorithm>
#include<iomanip>

using namespace std;

int n, ans = 0;
long long a, b;
vector<long long> t;

int main() {
	cin >> n >> a >> b;
	t.resize(n);
	for (int i = 0; i < n; i++)
		cin >> t[i];

	//sort(t.begin(), t.end());
	for (int i = 0; i < n; i++) {
		if (t[i] < a || b <= t[i])
			ans++;
	}

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

Measured memory_bytes: 256
N = int(input())
xl = [list(map(int,input().split())) for x in range(N)]
r_list = []

for i in range(N):
    a = max(0, xl[i][0] - xl[i][1])
    b = xl[i][0] + xl[i][1]
    r_list.append([b, a])
r_list.sort()

count = 0
tail = 0

for j in range(N):
    if r_list[j][1] >= tail:
        count += 1
        tail = r_list[j][0]
print(count)

Measured memory_bytes: 41440
#include <bits/stdc++.h>
using namespace std;
#define MOD 998244353
#define ff first
#define ss second
typedef long long ll;
ll power(ll a, ll b){//a^b
    ll res=1;
    a=a%MOD;
    while(b>0){
        if(b&1){res=(res*a)%MOD;b--;}
        a=(a*a)%MOD;
        b>>=1;
    }
    return res;
}
ll fermat_inv(ll y){return power(y,MOD-2);}
ll gcd(ll a, ll b){return (b==0)?a:gcd(b,a%b);}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t=1;
    //cin>>t;
    while(t--){
        ll a,b,c,k;
        cin>>a>>b>>c>>k;
        ll ans=0;
        ans+=min(a,k);
        int v2=min(a,k);
        a-=v2;
        k-=v2;
        v2=min(b,k);
        b-=v2;
        k-=v2;
        ans-=min(c,k);
        v2=min(c,k);
        c-=v2;
        k-=v2;
        cout<<ans<<"\n";
    }
    return 0;
}

Measured memory_bytes: 3580
a, b = map(int, input().split())
if a == 1 and a != b:
    print("Alice")
    exit()
if b == 1 and a != b:
    print("Bob")
    exit()
if a < b:
    print("Bob")
    exit()
if a > b:
    print("Alice")
    exit()
if a == b:
    print("Draw")

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;
using vll = vector<long long>;
using vp = vector<pair<int, int>>;
using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;
using vvll = vector<vector<long long>>;
template<class T> inline bool chmax(T &a, T b) { if (a<b) {a=b; return 1;} return 0;}
template<class T> inline bool chmin(T &a, T b) { if (b<a) {a=b; return 1;} return 0;}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    vll a(n);
    rep(i, n) cin >> a[i];
    vll l(n+1), r(n+1);
    l[n] = 2;
    r[n] = 2;
    for (int i = n-1; i >= 0; --i) {
        ll mn = (l[i+1] + a[i] - 1) / a[i] * a[i];
        ll mx = r[i+1] / a[i] * a[i];
        if (!(mn <= mx)) {
            cout << -1 << endl;
            return 0;
        }
        l[i] = mn;
        r[i] = mx + a[i] - 1;
    }
    cout << l[0] << " " << r[0] << endl;
    // if (a[n-1] != 2) {
    //     cout << -1 << endl;
    //     return 0;
    // }
    // ll pre = 2;
    // for (int i = n-2; i >= 0; --i) {
    //     ll nxt = ((pre + a[i] - 1) / a[i]) * a[i];
    //     if ((nxt / a[i+1]) * a[i+1] != pre) {
    //         cout << -1 << endl;
    //         return 0;
    //     }
    //     pre = nxt;
    // }
    // ll mn = pre;
    
    // pre = 2;
    // for (int i = n-2; i >= 0; --i) {
    //     ll nxt = ((pre + a[i] - 1) / a[i]) * a[i];
    //     while (((nxt + a[i]) / a[i+1]) * a[i+1] == pre) nxt += a[i];
    //     pre = nxt;
    // }
    // ll mx = pre + a[0] - 1;
    // cout << mn << " " << mx << endl;
}

Measured memory_bytes: 2560
N, M = map(int, input().split())
array = list(map(int, input().split()))
array.sort()
diff = [0] * (M-1)
for i in range(M-1):
    diff[i] = abs(array[i+1] - array[i])
diff.sort(reverse=True)
for i in range(N-1):
    if len(diff) == 0:
        break
    diff.pop(0)
print(sum(diff))

Measured memory_bytes: 14088
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
using namespace std;

int dp[52][52];
int W,H;
int map[52][52];

int main(){

  cin >> H >> W;
    
    //テ・ツ?・テ・ツ環?
    char tmp[100];
    for(int i = 0; i < H ; i++){
      cin >> &tmp[0];
      for(int j = 0; j < W ; j++){
	char x = tmp[j+1];
	tmp[j+1] = '\n';
	map[i][j] = atoi(&tmp[j]);
	tmp[j+1] = x;
      }
    }
    /*   
    for(int i = 0; i < H ; i++){
      for(int j = 0; j < W ; j++){
	cout << map[i][j];
      }
      cout << endl;
    }
    */
    dp[0][0] = map[0][0];
    for(int i = 0; i < H ; i++){
      for(int j = 0; j < W ; j++){
	if(i == 0 && j == 0) continue;
	if(i == 0)
	  dp[i][j] = dp[i][j-1] + map[i][j];
	else if(j == 0)
	  dp[i][j] = dp[i-1][j] + map[i][j];
	else
	  dp[i][j] = min( dp[i-1][j] , dp[i][j-1]) + map[i][j];
      }
    }
    
    /*
      for(int i = 0; i < H ; i++){
      for(int j = 0; j < W ; j++){
      cout << dp[i][j] << " ";
      }
      cout << endl;
      }
    */
    cout << dp[H-1][W-1] - map[H-1][W-1] - map[0][0] << endl;
  
  return 0;
}

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

int main() {
  
  long long n;
  cin >> n;
  
  vector<long long> vec1(10*10*10*10*10*10);
  vector<long long> vec2(10*10*10*10*10*10);
  int s=0;
  for (int i=0; i<10*10*10*10*10*10/*==10^6*/; i++) {
    if (n%(i+1)==0) {
      vec1.at(s)=i+1;
      vec2.at(s)=n/(i+1);
      s++;
    }
  }
  
  vector<long long> vec3(10*10*10*10*10*10);
  for (int i=0; i<10*10*10*10*10*10; i++) vec3.at(i)=vec1.at(i)+vec2.at(i);
  
  long long t=10000000000000;
  for (int i=0; i<s; i++) t=min(t,vec3.at(i));
  
  cout << t-2 << endl;
}

Measured memory_bytes: 23680
#include<iostream>
#include<algorithm>
using namespace std;
int n,k,s,a[5010],f[5010];
int main(){
	cin>>n>>k;
	for(int i=0;i<n;i++){
		cin>>a[i];
		a[i]=min(a[i],k);
		s+=a[i];
	}
	sort(a,a+n+1);
	f[0]=1;
	for(int i=n;i>=0;i--){
		bool v=true;
		for(int j=k-1;j>=k-s&&j>=0;j--){
			if(f[j]){
				v=false;
			}
		}
		if(v){
			cout<<i<<endl;
			return 0;
		}
		for(int j=k;j>=a[i];j--){
			f[j]|=f[j-a[i]];
		}
		s-=a[i];
	}
	return 0;
}


Measured memory_bytes: 256
// by batr (TBhero.17)                      
// This will be Accepted!
// why am I so dumb ? :c
 
#include <bits/stdc++.h>
 
#define jyldam ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
 
#define pb push_back
#define mp make_pair
 
#define B begin()
#define E end()
#define sz size()
#define skip continue
#define all(x) (x).begin(), (x).end()
 
#define ai a[i]
#define F first
#define S second          
 
#define st(x) st+=x
#define pli pair<long long, int>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;     
 
const int N = 1e6 + 17, M = N * 4, D = 2e3 + 17, mod = 1e9 + 7;
const ll INF = 1e17 + 17;
 
int tt = 1;  
int n, x;
int a[D][D];
ll b[D][D];
ll ans;
 
void solve () {          
			cin >> n >> x;
			for (int i = 1; i <= n; i++) {
					cin >> a[i][0];
					ans += a[i][0];
			}		                 
			for (int k = 1; k < n; k++) {
					ll lol = k * 1ll * x;
					for (int i = 1; i <= n; i++) {
							int id = i;
							if (id > 1) {
								id--;
							}
							else {
								id = n;
							}
							a[i][k] = min(a[i][0], a[id][k-1]);
							lol += a[i][k];
					}
					ans = min(lol, ans);
			}
			cout << ans;
}
		
int main() {
		jyldam;   
                  
		while (tt--) {   
			solve();
		}
   	
		return 0;
}

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

int main(){
	string S;
	cin >> S;
	int N=S.size()+1;
	vector<int> a(N,0);
	
	int c=0;
	for(int i=0;i<N-1;i++){
		if(S[i]=='<')c++;
		else c=0;
		a[i+1]=max(a[i+1],c);
	}
	c=0;
	for(int i=N-2;i>=0;i--){
		if(S[i]=='>')c++;
		else c=0;
		a[i]=max(a[i],c);
	}
	long long ans=0;
	for(auto i:a)ans+=i;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 2820
#include <iostream>
using namespace std;
int main(){

  int n,a[1000],r=-1;
  cin>>n;
  for(int i=0;i<n;i++) cin>>a[i];
  for(int i=0;i<n;i++){
    for(int j=i+1;j<n;j++){
      int a0=a[i]*a[j],t=0;
      int ch=a0%10;
      a0/=10;
      for(;a0&&a0%10;){
	if(a0%10!=ch-1) t++;
	ch--;
	a0/=10;
      }
      if(!t&&!a0) r=max(r,a[i]*a[j]);
    }
  }
  cout<<r<<endl;
  return 0;
}

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

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


int main() {
    int D,T,S;
    cin >> D >> T >> S;
    if(D <= T * S){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}

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

typedef long long ll;
typedef unsigned long long ull;

int main(){
    int num[6];
    for(int i=0;i<6;i++) cin >> num[i];
    int t=1,n=5,e=3;

    string s;
    cin >> s;
    for(int i=0;i<s.size();i++){
        int tp=t,np=n,ep=e;
        if(s[i]=='N'){
            t=7-np;
            n=tp;
        }
        if(s[i]=='E'){
            t=7-ep;
            e=tp;
        }
        if(s[i]=='S'){
            t=np;
            n=7-tp;
        }
        if(s[i]=='W'){
            t=ep;
            e=7-tp;
        }
    }

    cout << num[t-1] << endl;    
    return 0;
}


Measured memory_bytes: 3180
#include <bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int N; cin >> N; 
	long long A[200010] = {}; 
	long long ans = 0; 
	for(int i = 0; i < N; i++) cin >> A[i]; 
	long long mx = A[0];
	for(int i = 1; i < N; i++){
		if(A[i] >= mx) mx = A[i]; 
		else ans += mx - A[i]; 
	}
	cout << ans << "\n"; 
}

Measured memory_bytes: 5176