akhauriyash/Code-Regression huggingface dataset:
#include <math.h>
#include <assert.h>
#include <algorithm>
#include <set>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <string>
#include <cstring>
#include <functional>
#include <stack>
#include <array>
#include <random>
#include <chrono>
#include <climits>
#include <bitset>
using namespace std ;
#define ld long double
#define int long long
#define ii pair<int,int>
#define FAST_IO ios_base::sync_with_stdio(false) ;cin.tie(NULL);cout.tie(NULL); clock_t beg = clock()
#define dbg(x) cerr << #x << " is " << x << endl;
#define ms(x,a) memset(x,(int)(a),sizeof(x))
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define vi vector<int >
#define pb push_back
#define endl '\n'
#define ff first
#define ss second
//const int N = 3e5+7 ;
//const int INF = 1e18 ;
//const int MOD = 1e9 + 7 ;


void solve(){
	int a , b , n ;
	cin >> a >> b >> n ;
	n = min(n,b-1) ;
	int ans = (a*n)/b - a * (n/b) ;
	cout << ans << endl ;
}

int32_t main(){
	FAST_IO ;
	int t = 1 ;
//	cin >> t ;
	while(t--){
		solve() ;
	}
    cerr << "\nExecution time: " << (clock() - beg) / 1000 << '\n';
}


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


Measured memory_bytes: 2048
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    if(n>=400&&n<=599)
        cout<<8<<endl;
    else if(n>=600&&n<=799)
        cout<<7<<endl;
    else if(n>=800&&n<=999)
        cout<<6<<endl;
    else if(n>=1000&&n<=1199)
        cout<<5<<endl;
    else if(n>=1200&&n<=1399)
        cout<<4<<endl;
    else if(n>=1400&&n<=1599)
        cout<<3<<endl;
    else if(n>=1600&&n<=1799)
        cout<<2<<endl;
    else if(n>=1800&&n<=1999)
        cout<<1<<endl;
    return 0;

}


Measured memory_bytes: 3668
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(void)
{
    char s[6];
    int i = 0;
    char c;
    for (i = 0; i < 6; i++) //文字列の読み込み
    {
        scanf("%c", &c);
        s[i] = c;
    }
    if ((s[2] == s[3]) && (s[4] == s[5]))
        printf("Yes\n");
    else
        printf("No\n");
    return 0;
}

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

__attribute__((constructor))
void fast_io() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

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

    vector<int> id(n);
    iota(id.begin(), id.end(), 0);
    sort(id.begin(), id.end(), [&](int i, int j) { return x[i] < x[j]; });

    dsu d(n);
    set<pair<int, int>> st;
    for (int i = 0; i < n; ++i) {
        int mn = y[id[i]];
        if (!st.empty()) {
            auto it = st.begin();
            while (it != st.end() && it->first < y[id[i]]) {
                mn = min(mn, it->first);
                d.merge(id[i], it->second);
                it = st.erase(it);
            }
        }
        st.emplace(mn, id[i]);
    }

    for (int i = 0; i < n; ++i) cout << d.size(i) << '\n';
}


Measured memory_bytes: 11072
package main

import (
	"fmt"
	"strings"
)

func main() {
	var n int
	var s string
	fmt.Scanf("%d\n", &n)
	fmt.Scanf("%s\n", &s)

	nw := strings.Count(s, "W")
	nr := strings.Count(s[len(s)-nw:], "R")
	fmt.Println(nr)
}


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

int main() {
  string s;
  cin >> s;
  string res = "AC";
  if (s[0] != 'A') {
    res = "WA";
  }
  int cnt = 0;
  for (int i = 1; i < s.size(); i++) {
    if (isupper(s[i])) {
      if (i == 1 || i == s.size() - 1 || s[i] != 'C') {
        res = "WA";
      }
      cnt++;
    }
  }
  if (cnt != 1) {
    res = "WA";
  }
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 3632
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <bitset>
#include <set>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)
#define all(i,n) (i),(i+n)

int dx4[4]={1,0,-1,0};
int dy4[4]={0,-1,0,1};
int dx8[8]={1,0,-1,1,-1,1,0,-1};
int dy8[8]={1,1,1,0,0,-1,-1,-1};

typedef pair<int, int> P;
typedef pair<string, int> SP;
typedef long long ll;

const int INF = 1e9;
const ll LLINF = 1e18;
const int MAX_V = 1e6+1;
const ll mod = 1000000007;

// --------------------------------------
int n, m;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin >> n >> m;

  vector<int> v(n + 1, 0);

  REP(i, m) {
    int a, b;
    cin >> a >> b;

    v[a]++;
    v[b]++;
  }

  bool f = true;
  FOR(i, 1, n + 1) {
    if(v[i] % 2 != 0) {
      f = false;
      break;
    }
  }

  cout << (f ? "YES" : "NO") << endl;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
const int N=200010,Mod=998244353;
const double pi=acos(-1.0);
typedef long long int ll;
typedef pair<int,int> pii;
int n,len,ans;
int main()
{
  cin>>n;
  int x=n;
  while(x>0)
  {
    len++;
    x/=10;
  }
  int num=1;
  for(int i=1;i<=len;i+=2)
  {
    int l=num;
    int r=10*num-1;
    if(n<=r) ans+=(n-l+1);
    else ans+=(r-l+1);
    num*=100;
  }
  cout<<ans<<endl;
  return 0;
}


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

int main() {
  int n, k, s;
  cin >> n >> k >> s;
  for (int i = 0; i < k; ++i) {
    if (i) cout << " ";
    cout << s;
  }
  for (int i = k; i < n; ++i) {
    if (i) cout << " ";
    cout << (s==1e9?1:(s+1));
  }
}

Measured memory_bytes: 1280
M = 100001
dp = {}
dp[100],dp[101],dp[102],dp[103],dp[104],dp[105] = 1,1,1,1,1,1
def isComb(dp,n):
	for i in range(100,106):
		for j in range(i,106):
			if n-i in dp and n-j in dp and dp[n-i]==1 and dp[n-j]==1:
				return 1
			
	return 0


for i in range(106,M):
	if isComb(dp,i):
		dp[i] = 1
	else:
		dp[i] = 0
n = int(input())
if n in dp:
	print(dp[n])
else:
	print(0)
# print(dp[n])


Measured memory_bytes: 15076
package main

import "fmt"

func diff(a, b int) int {
	if a > b {
		return a - b
	}
	return b - a
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

func solve(as []int, next int) int {
	sum := 0
	count := 0
	for _, a := range as {
		sum += a
		if next*sum <= 0 {
			count += diff(sum, next)
			sum = next
		}
		next *= -1
	}
	return count
}

func main() {
	var n int
	fmt.Scan(&n)
	as := make([]int, n)
	for i := range as {
		fmt.Scan(&as[i])
	}

	fmt.Println(min(solve(as, 1), solve(as, -1)))
}


Measured memory_bytes: 5504
#include <bits/stdc++.h>
#include <string>
#define INF 100000
using namespace std;
int H, W, N;
int sx, sy;
typedef long long ll;
int main(){
    cin >> N;
    int ans;
    ans = N/2;
    float kotae;
    kotae = (double) ans/N;
    cout << 1-kotae <<endl;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define GET_ARRAY_SIZE(a)   (sizeof(a)/sizeof(a[0]))
int main(){
    int k_num[] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
    int k;
    cin >> k;
    cout << k_num[k-1] << endl;

}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int a[1001];
int main()
{
    bool f;
    int n,q;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    cin>>q;
    for(int i=0;i<q;i++)
    {
        int b,e,t,j;
        cin>>b;cin>>e;cin>>t;
        for(j=0;j<n;j++)
        {
            if(j>=b&&j<e)
                swap(a[j+t-b],a[j]);
        }
    }
        f=false;
        for(int j=0;j<n;j++)
        {
            if(f==true)
                cout<<" "<<a[j];
            else
            {
                f=true;
                cout<<a[j];
            }
        }
        cout<<"\n";
}


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

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int cnt[100];

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

	int N,M; cin >> N >> M;

	for (int i = 0;i < N;i++){
		int K; cin >> K;
		for (int j = 0;j < K;j++){
			int tmp; cin >> tmp;
			cnt[tmp]++;
		}
	}

	int ans = 0;

	for (int i = 1;i <= M;i++){
		if(cnt[i] == N) ans++;
	}

	cout << ans << endl;

	return 0;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<ll,ll> P;
#define M 1000000007
#define F first
#define S second
#define PB push_back
#define INF 100000000000000000
ll n,k,dp[105][200005],a[105];
int main(void){
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<=n;i++)scanf("%lld",a+i);
    dp[0][k]=1;
    for(int i=1;i<=n;i++){
        for(int j=k-1;j>=0;j--)dp[i-1][j]=(dp[i-1][j]+dp[i-1][j+1])%M;
        for(int j=0;j<=k;j++){
            dp[i][j]=(dp[i-1][j]-dp[i-1][j+a[i]+1]+M)%M;;
        }
    }
    printf("%lld\n",dp[n][0]);
}


Measured memory_bytes: 157184
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
#include <functional>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

template<typename T> void chmin(T &a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T &a, T b) { if (a < b) a = b; }

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

const ll INF = 1e17;

template<typename T>
struct SegmentTree{
    int n, width;
    vector<T> dat;

    void init(int x){
        n = x;
        width = 1;
        while (width < n) width *= 2;
        dat.assign(2*width-1, INF);
    }

    void update(int i, T x){
        i += width - 1;
        dat[i] = x;
        while (i > 0){
            i = (i - 1) / 2;
            dat[i] = min(dat[i*2+1], dat[i*2+2]);
        }
    }

    T query(int a, int b, int k, int l, int r){
        if (r <= a || b <= l) return INF;
        if (a <= l && r <= b) return dat[k];
        T vl = query(a, b, k*2+1, l, (l+r)/2);
        T vr = query(a, b, k*2+2, (l+r)/2, r);
        return min(vl, vr);
    }

    // [l, r)
    T query(int l, int r){
        return query(l, r, 0, 0, width);
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    VVL l2r(n), l2c(n);
    REP(i,m){
        int l = in() - 1, r = in(), c = in();
        l2r[l].push_back(r);
        l2c[l].push_back(c);
    }

    SegmentTree<ll> seg;
    seg.init(n);
    seg.update(0, 0);

    REP(i,n-1){
        ll x = seg.query(i, n);
        if (x == INF){
            cout << -1 << endl;
            return 0;
        }
        REP(j,l2r[i].size()){
            int r = l2r[i][j] - 1;
            ll c = l2c[i][j];
            if (seg.query(r, r + 1) > x + c){
                seg.update(r, x + c);
            }
        }
    }
    ll ans = seg.query(n - 1, n);
    if (ans == INF) ans = -1;
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 13056
#include<bits/stdc++.h>
using namespace std;    
#define ll long long
int main() {
    ios_base::sync_with_stdio(false), cin.tie(0);
    int n;
    cin >> n;
       for(int i = 1000; ; i += 1000) {
            if(i >= n) {
                n = i - n;
                break;
            }
        }
    cout << n;
} 

Measured memory_bytes: 3648
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

using boost::multiprecision::cpp_int;
using namespace std;

#if __has_include("print.hpp")
  #include "print.hpp"
#endif

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define MOD 1000000007

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; }

typedef long long ll;
typedef pair<ll, ll> p;


int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int a, b;
  cin >> a >> b;
  for (long double i = 1; i < 50100; i++) {
    if(int(i * 0.08) == a && int(i * 0.1) == b){
      cout << int(i) << endl;
      return 0;
    }
  }
  cout << -1 << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll ksm(ll x,ll y){
    ll res=1;
    while(y){
        if(y&1) res=res*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return res%mod;
}
ll cal(ll a,ll b){
    ll res=1;
    ll res2=1;
    for(ll i=a;i>=(a-b+1);i--) res=res*i%mod;
    for(ll i=1;i<=b;i++) res2=res2*i%mod;
    return res*ksm(res2,mod-2)%mod;
}
int main()
{
    ll n,a,b;
    cin>>n>>a>>b;
    ll ans=(ksm(2,n)-1+mod)%mod;
    cout<<(ans-cal(n,a)+mod-cal(n,b)+mod)%mod<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
// #define int long long int
double calcAngle(double h, double m)
{

    if (h == 12)
        h = 0;
    if (m == 60)
        m = 0;

    // Calculate the angles moved by hour and minute hands
    // with reference to 12:00
    double hour_angle = 0.5 * (h * 60 + m);
    double minute_angle = 6 * m;

    // Find the difference between two angles
    double angle = abs(hour_angle - minute_angle);

    // Return the smaller angle of two possible angles
    angle = min(360 - angle, angle);

    return angle;
}
int32_t main()
{
    double pi =3.141592653589793238;
    double a, b;
    double h, m;
    cin >> a >> b >> h >> m;
    double angle = calcAngle(h, m);
    // cout << angle << endl;
    // cout << "cos " << cos(angle) << endl;
    double ans = sqrt(a * a + b * b - 2 * a * b * cos(angle * (pi / 180)));
    printf("%0.21f", ans);
    cout << endl;
    return 0;
}

Measured memory_bytes: 4224
#include <bits/stdc++.h>
#define FOR(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define FORR(i, n) for(ll i = (ll)n - 1LL; i >= 0LL; i--)
#define rep(i, n) FOR(i, 0, n)
#define ALL(x) begin(x), end(x)
using namespace std;
using ll = long long;
template <typename T> using V = vector<T>;
constexpr int Mod = 998244353;
constexpr int mod = 1e9 + 7;
constexpr ll inf = 1LL << 60;
template <typename T> constexpr bool chmax(T &a, const T &b) {
    if(a >= b) return false;
    a = b;
    return true;
}
template <typename T> constexpr bool chmin(T &a, const T &b) {
    if(a <= b) return false;
    a = b;
    return true;
}

/*-------------------------------------------*/

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

    int a, b;
    int k;
    cin >> k >> a >> b;
    for(int i = a; i <= b; i++)
        if(i % k == 0) {
            puts("OK");
            return 0;
        }
    puts("NG");

    return 0;
}

Measured memory_bytes: 3656
import fractions
import math
n,m = map(int,input().split())
l = list(map(int,input().split()))
count = 0
while True:
    if l[0] % 2 == 0:
        l[0] //= 2
        count += 1
    else:
        break

for i in range(1,n):
    l[i] //= 2**count
    if l[i] % 1 != 0 or l[i] % 2 == 0:
        print(0)
        exit()
    

ans = l[0]
for i in range(1,n):
    ans = ans * l[i] //fractions.gcd(ans,l[i])

ans1 = (m//2**(count-1))//ans


if ans1 % 2 == 0:
    print(ans1//2)
else:
    print(ans1//2+1)


Measured memory_bytes: 16280
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <numeric>
//#include <stdio.h>
//#include <stack>
//#include <queue>
#include <cstdio>
#include <cmath>
#include <iterator>
#include <map>
//#include <fstream>
//#include <list>
//#include <iomanip>
#include <stdlib.h>
#include <cctype>

using namespace std;

#define MOD 1000000007
#define Int int64_t
#define PI 3.14159265358979
#define ssort(z) sort(z.begin(),z.end())
#define rsort(z) sort(z.rbegin(),z.rend())
#define eerase(z) z.erase(unique(z.begin(),z.end()),z.end())
#define ccnt(z,w) count(z.begin(),z.end(),w)


void printVec(std::vector<int> & vec) {
	std::cout << "";
	for (auto it = vec.begin(); it != vec.end(); ++it) {
		std::cout << *it << " ";
	}
	std::cout << std::endl;
}
void printVec1(std::vector<string>& vec) {
	std::cout << "";
	for (auto it = vec.begin(); it != vec.end(); ++it) {
		std::cout << *it << " ";
	}
	std::cout << std::endl;
}
void printVec2(std::vector<Int>& vec) {
	std::cout << "";
	for (auto it = vec.begin(); it != vec.end(); ++it) {
		std::cout << *it << " ";
	}
	std::cout << std::endl;
}

Int gcd(Int a, Int b) {
	return b != 0 ? gcd(b, a % b) : a;
}
Int lcm(Int a, Int b) {
	return a / gcd(a, b) *b;
	//a*bは64bit integer overflow
}

bool comp(const string a, const string b) {
	return a.length() < b.length();
}

bool integer(double num) {
	return floor(num) == num;
}

string gen(int num) {
	string str = "";
	for (int i = 0; i < num; i++) str += ".";
	return str;
}
Int fact(int num) {
	if (num == 0) return 1;
	else return num * fact(num - 1);
}


int main() {
	int a, b, c, d; cin >> a >> b >> c >> d;
	if (a + b < c + d) cout << "Right";
	else if (a + b > c + d) cout << "Left";
	else cout << "Balanced";
	


	cout << endl;
	return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
import sys

def cum_xor(n):
    ret = 0
    if n % 4 == 1 or n % 4 == 2:
        ret += 1
    i = 1
    while n >= 2 ** i:
        tmp = n % (2 ** (i + 1))
        if tmp >= 2 ** i and tmp % 2 == 0:
            ret += 2 ** i
        i += 1
    return ret

def solve(A: int, B: int):
    ret = cum_xor(A - 1) ^ cum_xor(B)
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    solve(A, B)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long ll;

using namespace std;

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

  int ans = (n%2 == 0) ? n/2 : n/2 +1;

  cout << ans << endl;
  
}


Measured memory_bytes: 256
import copy
from itertools import combinations
h, w, k = map(int, input().split())
c =[input() for i in range(h)]
su = 0
for i in range(h):
    for j in range(w):
        if c[i][j] == "#":
            su += 1
ans = 0
y = []
for i in range(h):
    y.append(i)
x = []
for i in range(w):
    x.append(i)
for i in range(h+1):
    ty = list(combinations(y, i))
    for j in range(w+1):
        tx = list(combinations(x, j))
        for l in ty:
            for m in tx:
                cnt = 0
                for p in l:
                    for q in m:
                        if c[p][q] == '#':
                            cnt += 1
                if cnt == k:
                    ans += 1
print(ans)

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

using namespace std;
#define ALL(x)              (x).begin(),(x).end()
#define REP(i, n)           for (int (i) = 0 ; (i) < (ll)(n) ; ++(i))
#define REPN(i, m, n)       for (int (i) = m ; (i) < (ll)(n) ; ++(i))
#define INF                 (int)2e9
#define MOD                 (1000 * 1000 * 1000 + 7)
#define Ceil(x, n)          (((((x))+((n)-1))/n))
#define CeilN(x, n)         (((((x))+((n)-1))/n)*n)
#define FloorN(x, n)        ((x)-(x)%(n))
#define IsOdd(x)            (((x)&0x01UL) == 0x01UL)
#define IsEven(x)           (!IsOdd((x)))
#define M_PI                3.14159265358979323846
typedef long long           ll;
typedef pair<ll, ll>        P;

/*-----------------------------------------------------------------------------
　処理
 -----------------------------------------------------------------------------*/
int main()
{
	int A, B, M;
	cin >> A >> B >> M;
	vector<int> a(A);
	vector<int> b(B);
	REP(i, A) cin >> a[i];
	REP(i, B) cin >> b[i];

	vector<int> x(M), y(M), c(M);
	REP(i, M) {
		cin >> x[i] >> y[i] >> c[i];
		x[i]--;
		y[i]--;
	}

	int ans = INF;
	REP(i, M) {
		int ansOne = a[x[i]] + b[y[i]] - c[i];
		ans = min(ansOne, ans);
	}

	sort(ALL(a));
	sort(ALL(b));
	ans = min(ans, a[0] + b[0]);

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 2176
MOD=10**9+7
cnt=0; sum=0; prev=nil; can=true; h=Hash.new(0)
def gs() gets.chomp end
def gi() gets.to_i end
def gsmi() gets.chomp.split.map(&:to_i) end

def desc(ar) ar.sort!{|x,y|y<=>x} end
def min(a,b) a<=b ? a : b end
def max(a,b) a>=b ? a : b end
def sum(ar) ar.inject(:+) end

def C(a,b) b==0||a==b ? 1 : (b=a-b if a/2<b;(a-b+1..a).inject(:*)/(1..b).inject(:*)) end

def puts_yesno(can) puts(can ? 'Yes' : 'No') end
def putsend(s) puts s; exit end
def debug(k,v) puts "#{k}:#{v}" end
########### ( ˘ω˘ )ｽﾔｧ… ###########
n,m=gsmi
a=m.times.map{gi}

Memo={}
Memo[0]=1
Memo[1]=1

a.each do |i|
  Memo[i]=0
end

1.upto(n) do |i|
  next if Memo[i]
  sum=(Memo[i-1]+Memo[i-2])%MOD
  Memo[i]=sum
end

puts Memo[n]

Measured memory_bytes: 9084
N, A, B = gets.split.map(&:to_i)
 
H = []
N.times{ H << gets.to_i }
 
def enough(i)
  i >= H.map{ |x| ( [(x - i * B), 0].max * 1.0 / (A - B) ).ceil }.inject(:+)
end
 
puts (1..(H.max*1.0/B).ceil).bsearch{ |i| enough(i) }

Measured memory_bytes: 17972
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let 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)*}
    };
}

#[allow(unused_macros)]
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)*}
    };
}

#[allow(unused_macros)]
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 dd(a: Vec<Vec<char>>, b: Vec<Vec<char>>, x: usize, y: usize) -> bool {
    for i in 0..b.len() {
        for j in 0..b.len() {
            if b[i][j] != a[i + x][j + y] {
                return false;
            }
        }
    }
    true
}

fn main() {
    input! {
        n: usize,
        m: usize,
        a: [chars; n],
        b: [chars; m],
    }
    for y in 0..n - m  + 1 {
        for x in 0..n - m + 1 {
            if dd(a.clone(), b.clone(), x, y) {
                println!("Yes");
                return;
            }
        }
    }
    println!("No");
}

Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define endl "\n"
#define speed() ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define sz(x) (int)(x).size()
#define _USE_MATH_DEFINES
using namespace std;
typedef long long int lli;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

int main() {
    speed();
    string s; cin >> s;
    int cnt = 0;
    rep(i, 0, s.size()) {
        if (s[i] == '0') {
            if (s[i] == s[i+1]) {
                s[i+1] = '1';
                cnt++;
            }
        }
        if (s[i] == '1') {
            if (s[i] == s[i+1]) {
                s[i+1] = '0';
                cnt++;
            }
        }
    }
    cout << cnt << endl;
    return 0;
}

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define fin(x) cout << x << endl;

using namespace std;
using ll = long long;

int main(void) {
  int n, k;
  cin >> n >> k;
  int i = 0;
  while (true) {
    if ((int)(pow(k, i)) - 1 >= n) {
      cout << i << endl;
      return 0;
    }
    i++;
  }
	return 0;
}



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

int main(){
  int N;
  cin >>  N;
  int s[N+100];
  int temp=0;
  for (int i=0;i<N;i++){
    cin >> s[i];
    temp=temp+s[i];
  }
  sort(s,s+N);
  if(!(temp%10==0)){
      cout<<temp<<endl;
      return 0;
    }
  for (int i=0;i<N;i++){
    if(s[i]%10==0){
      continue;
    }
    else{
      cout<<temp-s[i]<<endl;
      return 0;
    }
  }

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

  

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

int main() {
    int N; cin >> N;
    int M; cin >> M;
    vector<pair<int, int> > B;
    rep(i, M){
        int a, b; cin >> a >> b;
        B.push_back(make_pair(a, b));
    }
    sort(B.begin(), B.end());

    queue<pair<int, int> > Q;
    int now = 0;
    rep(i, M){
        if(B[i].first != now){
            Q.push(B[i]);
            now = B[i].first;
        }
    }

    pair<int, int> p2 = Q.front(); Q.pop();
    int l = p2.first;
    int r = p2.second;
    int ans = 1;

    while(!Q.empty()){
        pair<int, int> p = Q.front(); Q.pop();
        if(r <= p.first){
            ans++;
            l = p.first;
            r = p.second;
        } else {
            l = max(l, p.first);
            r = min(r, p.second);
        }
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 1908
#include <stdio.h>

int main(void)
{
	int N, K, X, Y;

	scanf("%d %d %d %d", &N, &K, &X, &Y);
	printf("%d\n", (N < K ? N : K) * X + (N - K < 0 ? 0 : N - K) * Y);

	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
using ll = long long int;

int main() {
    int h, w, n; cin >> h >> w >> n;
    int ans = h;
    unordered_map<ll, int> field;
    vector<vector<int>> block(h);
    for(int i=0; i<n; i++){
        int x, y; cin >> x >> y;
        x--; y--;
        field[1LL * x * 1e6 + y] = 1;
        if(x > y){
            block[x].push_back(x - y);
        }
    }
    int rank = 1;
    for(int i=0; i<h; i++){
        for(auto& v:block[i]){
            if(v >= rank){
                cout << i << endl;
                return 0;
            }
        }
        if(field[1LL * i * 1e6 + (i - rank + 1)] == 1){rank++;}
    }
    cout << ans << endl;
    return 0;
}

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

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

        try{
            //入力
            int N = scan.nextInt();
            int M = scan.nextInt();
            int[] X_ = new int[M];
            for(int i = 0; i < M; i++){
                X_[i] = scan.nextInt();
            }

            //入力地点ソート
            Arrays.sort(X_);
            int dist = getDistance(X_, M, N);

            System.out.println(dist);

        }finally{
            scan.close();
        }
    }

    static int getDistance(int[] A, int m, int n){
        //地点ごとの距離入力
        int[] B = new int[m-1];
        for(int i = 0; i < m-1; i++){
            B[i] = A[i+1]-A[i];
        }
        Arrays.sort(B);

        int sum = 0;
        for(int i = 0; i < m-n; i++){
            sum += B[i];
        }
        return sum;
    }
}


Measured memory_bytes: 49712
import java.util.*;
public class Main {
    public static void main(String[]args){
        Scanner sc = new Scanner(System.in);

        int A = sc.nextInt();
        int B = sc.nextInt();

        sc.close();

        
        if (B == 1) {
            System.out.println(0);
        } else if(A>=B){
            System.out.println(1);
        } else{
            int ans = 0;
            while (true){
                B = B - (A-1);
                ans++;
                if (B <= A){
                    break; 

                }
            }
            System.out.println(ans+1);
        }
    }
       
}       

Measured memory_bytes: 21844
#include <iostream>

using namespace std;

int main()
{
    int N,M; cin >> N >> M;
    int ar[N];
    int v=0;
    for(int i=0;i<N;i++){
        cin >> ar[i];
        v += ar[i];
    }
    int c=0;
    for(int i=0;i<N;i++){
        if(ar[i]*4*M >=v){
            c++;
        }
    }
    if(c>=M){
        cout << "Yes";
    }
    else{
        cout << "No";
    }

    return 0;
}


Measured memory_bytes: 256
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <bitset>
#include <complex>

#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#define rep(i,n) for(int i=0;i<(n); i++)
#define rep2(i,n) for(int i=1;i<=(n);i++)
#define WHITE 0
#define GRAY 1
#define BLACK 2

using namespace std;
typedef long long ll;
const int NMAX = 100;
const int k = 200000;
static const int INF = 1<<21;
string s,t,ans;
int dp[3001][3001];
ll gcd(ll a, ll b){
if(a<b) swap(a,b);
    if(b==0) return a;
    return gcd(b, a%b);
}
int n,M[NMAX+1][NMAX+1]={0};
int d[NMAX]; //距離で訪問状態を管理(d[NMAX]={INFでは初期化できない!?})

void bfs(int s){
    queue<int> q;
    q.push(s);
    rep2(i,n){
        d[i]=INF;
    }
    d[s]=0;
    int u;
    while(!q.empty()){ //空でない限り
        u=q.front();q.pop();
        rep2(v,n){
            if(M[u][v]==0) continue;
            if(d[v]!=INF) continue;
            d[v]=d[u]+1; //距離は今考えているところより1大きい値
            q.push(v);
        }
    }
    rep2(i,n){
        cout << i << " " << ((d[i] == INF) ? (-1): d[i]) << endl;
        //INFのままだったら-1を出力
    }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(0); //この2行はより速度を向上させる
    // 追加２, 以降 cin の入力元が 'input.txt' になる

    int u,v,k;
    cin >> n;
    rep2(i,n){
        int u,k;
        cin >> u >> k;
        int v[k+1];
        rep2(j,k) cin >> v[j];
        rep2(j,k){
            M[i][v[j]]=1;
        }
    }
    bfs(1);
    return 0;
}


Measured memory_bytes: 3208
import sys
sys.setrecursionlimit(10 ** 9)

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rank = [0]*(n+1)

    def find(self, x):#親となる要素を探索
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find(self.root[x])#再帰
            return self.root[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return

        elif self.rank[x] > self.rank[y]:#深い木に連結
            self.root[x] += self.root[y]
            self.root[y] = x#yの親をxとする

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    def issame(self, x, y):#x, yが同じ集合か判定
            return self.find(x) == self.find(y)


    def count(self, x):#要素の個数
        return (-1)*self.root[self.find(x)]

n, m = map(int, input().split())
uf = UnionFind(n)

for i in range(m):
    a, b = map(int, input().split())
    uf.unite(a, b)

ans = 0

for i in range(n):
    ans = max(ans, uf.count(i))

print(ans)

Measured memory_bytes: 14544
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 100005

using namespace std;

int n;
int dp[MAX_N];

int main()
{
	scanf("%d",&n);
	memset(dp,0x3f,sizeof(dp));
	dp[0]=0;
	for(int i=1;i<=n;i++)
	{
		dp[i]=min(dp[i],dp[i-1]+1);
		for(int j=6;j<=i;j*=6) dp[i]=min(dp[i],dp[i-j]+1);
		for(int j=9;j<=i;j*=9) dp[i]=min(dp[i],dp[i-j]+1);
	}
	printf("%d\n",dp[n]);
}


Measured memory_bytes: 640
N = int(input())
line = input().split(" ")
A = [int(line[i]) for i in range(N)]
#print(A)

maxVal = 0
count = 0
for i in range(N):
    if A[i] == 1:
        count+=1
        if maxVal < count:
            maxVal = count
    else:
        count = 0
print(maxVal+1)



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

typedef long long int ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<string>vst;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;

#define fastio ios_base::sync_with_stdio(false);cin.tie(0);
#define all(ct) ct.begin() , ct.end()
#define endl "\n"
#define fr(i,a) for(auto i:a)
#define f(i,a,b) for(int i=a;i<b;++i)
#define fd(i,a,b) for(int i=a;i>=b;--i)
#define pb push_back
#define in(d,v) d.find(v)!=d.end()
#define mp make_pair
#define size(a) int(a.size())

const ll mod = 1e9 + 7;
const ll inf = ll(1e18);
const double PI = acos(-1);

ll modexp(ll x, ll n, int md) {
    if (n == 0)return 1;
    if (n % 2 == 0)return modexp((x * x) % md, n / 2, md);
    return (x * modexp((x * x) % md, n / 2, md)) % md;
}


int main(){
    fastio;
    //clock_t tm = clock();
    ll n,k;
    cin>>n>>k;
    vl a(n);
    f(i,0,n)cin>>a[i];
    ll l=1,r=1e9,m,ans=1e9;
    while(l<=r){
        m=(l+r)/2;
        ll ct=0;
        f(i,0,n){
           ct+=(a[i]-1)/m;
        }
        if(ct<=k){
            ans=m;r=m-1;
        }
        else{
            l=m+1;
        }
    }
    cout<<ans<<endl;
    //cout<<((clock()-tm)*1.0)/CLOCKS_PER_SEC<<endl;
}

Measured memory_bytes: 4752
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll L,a,b,mod;
struct Matric
{
    ll a[3][3];
    Matric(){memset(a,0,sizeof(a));}
    Matric operator*(const Matric&o)const
    {
        Matric ans;
        for(int i=0;i<3;i++)
            for(int j=0;j<3;j++)
                for(int k=0;k<3;k++)
                {
                    ans.a[i][j]=(ans.a[i][j]+a[i][k]*o.a[k][j]%mod)%mod;
                }
        return ans;
    }
};
Matric Mqpow(Matric a,ll n)
{
    Matric base=a;
    Matric ans;
    ans.a[0][0]=1,ans.a[1][1]=1,ans.a[2][2]=1;
    while(n)
    {
        if(n&1)
            ans=ans*base;
        base=base*base;
        n>>=1;
    }
    return ans;
}
ll qpow(ll a,ll n)
{
    ll base=a;
    ll ans=1;
    while(n)
    {
        if(n&1)
            ans=ans*base%mod;
        base=base*base%mod;
        n>>=1;
    }
    return ans;
}
int getlen(ll x)
{
    int ans=0;
    while(x)
    {
        x/=10;
        ans++;
    }
    return ans;
}
ll getpos(int x)
{
    ll l=1,r=L,ans=1;;
    while(l<=r)
    {
        ll m=l+r>>1;
        if(getlen(a+b*(m-1))<=x) l=m+1,ans=m;
        else r=m-1;
    }
    return ans;
}
int main()
{
    scanf("%lld%lld%lld%lld",&L,&a,&b,&mod);
    ll ans=a%mod;
    ll res=a%mod;
    ll now=1;
    for(int i=1;i<=18;i++)
    {
        ll p=getpos(i);
        if(p==now) continue;
        Matric A;
        A.a[0][0]=qpow(10,i),A.a[0][1]=1,A.a[0][2]=1;
        A.a[1][1]=1,A.a[1][2]=1,A.a[2][2]=1;
        A=Mqpow(A,p-now);
        ans=(A.a[0][0]*ans%mod+A.a[0][1]*res%mod+b%mod*A.a[0][2]%mod)%mod;
        res=(res+b%mod*(p-now)%mod)%mod;
        now=p;
    }
    printf("%lld\n",ans);
    return 0;
}


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

#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define ALL(a) (a).begin(),(a).end()

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

    REP(i, n) {
        vector<int> v(3);
        REP(j, 3) {
            cin >> v[j];
        }
        sort(ALL(v));
        if (pow(v[0],2)+pow(v[1],2)==pow(v[2],2)) cout << "YES" << endl;
        else cout << "NO" << endl; 
    }
    return 0;
}

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

typedef long long ll;
typedef long double ld;
#define size(a) int((a).size())
#define present(c, x) (c.find(x) != c.end()) 

int main() {
	std::ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n,m; cin >> n >> m;
	int final_start, final_end;
	cin >> final_start >> final_end;
	for (int i = 1; i<m && final_start <= final_end; i++) {
		int curr_start, curr_end; cin >> curr_start >> curr_end;
		final_start = max(final_start, curr_start);
		final_end = min(final_end, curr_end);
	}
	cout << max(final_end - final_start + 1, 0) << '\n';
	
}



Measured memory_bytes: 3672
n = int(input())
temp = list(map(int, input().split()))
l = [0]*n
ans = 0
for i in range(n):
  if temp[i] == i+1:
    l[i] = 0
  else:
    l[i] = 1

for i in range(n):
  if l[i] == 0 and i == n-1:
    ans += 1
  if l[i] == 0 and not i == n-1:
    l[i] = 1
    l[i+1] = 1
    ans += 1

print(ans)

Measured memory_bytes: 14008
D = ['dream', 'dreamer', 'erase', 'eraser']

S = input()
dp = [False] * (len(S)+1)
dp[0] = True
for i in range(len(S)):
  if not dp[i]:
    continue
  for d in D:
    if S[i:i+len(d)] == d:
      dp[i+len(d)] = True

if dp[len(S)]:
  print('YES')
else:
  print('NO')


Measured memory_bytes: 3956
#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include<algorithm>
#include<string>
#include <map>
#include <queue>
#include <stack>
#include <set>

#define DIV 1000000007
using namespace std;
using ll = long long;

typedef struct {
    vector<int> edge;
    int clr;
    int visit;
}node_t;
vector<node_t> node;

queue<int> q;
bool judge() {
    int x = q.front();
    q.pop();

    for (auto to : node[x].edge) {
        if (node[to].visit) {
            if (node[x].clr == 1 && node[to].clr == 1)
                return false;
            else if (node[x].clr == -1 && node[to].clr == -1)
                return false;
        }

        else {
            q.push(to);
            node[to].visit = 1;
            if (node[x].clr == 1)
                node[to].clr = -1;
            else if (node[x].clr == -1)
                node[to].clr = 1;
        }
    }
    if (!q.empty())
        return judge();
    return true;
}

int main() {
    ll N, M;
    cin >> N >> M;
    node = vector<node_t>(N + 1);

    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        node[a].edge.push_back(b);
        node[b].edge.push_back(a);
    }
    q.push(1);
    node[1].clr = 1;
    node[1].visit = 1;

    if (judge()) {
        ll B = 0, W = 0;
        for (int i = 1; i <= N; i++) {
            if (node[i].clr == 1) B++;
            else if (node[i].clr == -1)W++;
        }
        cout << B * W - M << endl;
    }
    else {
        cout << N * (N - 1) / 2 - M << endl;
    }
}


Measured memory_bytes: 11264
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
 
#define sl(x) scanf("%ld", &x)
#define ss(x) scanf("%s", x)
#define pl(x) printf("%ld\n", x)
#define pd(x) printf("%lf\n", x)
#define ps(x) printf("%s\n", x)
 
#define INF 1000000000000000000
#define MOD 1000000007

#define MIN(a,b) (((a)<(b))?(a):(b))
#define MAX(a,b) (((a)>(b))?(a):(b))

int compare_long(const void *a, const void *b) {
	return *(long*)b - *(long*)a;
}

int next(long r, long D, long x) {
  return r * x - D;
}

int main() {
	long N;
  long i, j;
  long r, D, x;
	long ans = 0;
	
  sl(r); sl(D); sl(x);
	
  for(i=1;i<=10;i++) {
    pl(x = next(r, D, x));
  }
	
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <string>
#include <numeric>
using namespace std;
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define ll long long

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

  cout << N-M+1 << endl;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int a[200][200],n=2,m,f[200][200];
int main()
{
	cin>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)cin>>a[i][j];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)f[i][j]=max(f[i-1][j],f[i][j-1])+a[i][j];
	cout<<f[n][m]<<endl;
	return 0;
}


Measured memory_bytes: 764
#include <bits/stdc++.h>
using namespace std;
template <class T> int size(const T &x) { return x.size(); }
#define rep(i,a,b) for (__typeof(a) i=(a); i<(b); ++i)
#define iter(it,c) for (__typeof((c).begin()) it = (c).begin(); it != (c).end(); ++it)
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long long ll;
const int INF = 2147483647;

int par[100100];
vi child[100100];
int dep[100100];

int ord[100100], oat = 0;
void dfs(int at) {
    ord[oat++] = at;
    iter(it,child[at]) {
        dfs(*it);
    }
}

int main() {
    int n, k;
    cin >> n >> k;
    int cnt = 0;
    rep(i,0,n) {
        cin >> par[i];
        par[i]--;
    }
    if (par[0] != 0) {
        cnt++;
        par[0] = -1;
    }
    rep(i,1,n) {
        child[par[i]].push_back(i);
    }
    dfs(0);
    for (int i = n-1; i > 0; i--) {
        int cur = ord[i];
        dep[cur] = 0;
        iter(it,child[cur]) {
            dep[cur] = max(dep[cur], 1 + dep[*it]);
        }
        // cout << cur+1 << " " << dep[cur] << endl;
        if (dep[cur] == k-1 && par[cur] != 0) {
            cnt++;
            dep[cur] = -1;
            // cout << "making 0" << endl;
        }
    }
    cout << cnt << endl;
    return 0;
}



Measured memory_bytes: 10112
import sys
read = lambda: sys.stdin.readline().rstrip()

def counting_tree(N, D):
    tot = 1
    
    # cnt = collections.Counter(D)
    cnt = [0]*N
    for i in D:
        cnt[i]+=1

    for i in D[1:]:
        tot = tot * cnt[i-1]%998244353

    return tot if D[0]==0 else 0

def main():
    
    N0 = int(read())
    D0 = tuple(map(int, read().split()))

    res = counting_tree(N0, D0)

    print(res)

if __name__ == "__main__":
    main()

Measured memory_bytes: 14148
import itertools
N,M=map(int,input().split())
x=[0 for i in range(N)]
y=[0 for i in range(N)]
z=[0 for i in range(N)]
for i in range(N):
    x[i],y[i],z[i]=map(int,input().split())
S=list(itertools.product([-1,1],repeat=3))
def num(seq):
    res=0
    for i in range(3):
        if seq[i]==1:
            res+=2**i
    return res
ans=0
for seq in S:
    A=[seq[0]*x[i]+seq[1]*y[i]+seq[2]*z[i] for i in range(N)]
    A.sort(reverse=True)
    tmp=0
    for i in range(M):
        tmp+=A[i]
    if tmp>ans:
        ans=tmp
print(ans)


Measured memory_bytes: 3188
head = gets
h = head.split(/ /)
min = 1
max = h[0].to_i
while line = gets
  break if line == "\n"
  l = line.split(/ /)
  if min < l[0].to_i
    min = l[0].to_i
  end
  if max > l[1].to_i
    max = l[1].to_i
  end
end

ans = max - min + 1
if ans > 0
  p ans
else
  p 0
end

Measured memory_bytes: 2428
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <list>
#include <set>
#include <numeric>
#include <queue>
#include <stack>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <climits>
#include <cfloat>
#include <ctime>
#include <complex>
#include <cassert>
#include <array>
#include <bitset> 
#include <unordered_map>

using namespace std;
typedef long long LL;
typedef pair<int,int> P;

const int L=1e5+10;
vector<int> ps[L];
bool done[L];
void dfs(int p)
{
	done[p]=true;
	for(int i:ps[p])
	{
		if(!done[i])
		{
			dfs(i);
		}
	}
}
int main() {
	int N,M;
	cin >> N >> M;
	for(int i=0;i<M;i++)
	{
		int a,b;
		cin >> a >> b;
		ps[a].push_back(b);
		ps[b].push_back(a);
	}
	int cnt4=0;
	int cnt6=0;
	vector<int> v4;
	for(int i=1;i<=N;i++)
	{
		if(ps[i].size()%2)
		{
			cout << "No" << endl;
			return 0;
		}
		if(ps[i].size()==4)
		{
			cnt4++;
			v4.push_back(i);
		}
		else if(ps[i].size()>4)
		{
			cnt6++;
		}
	}
	if(cnt4==2&&cnt6==0)
	{
		done[v4[1]]=true;
		dfs(v4[0]);
		for(int i=1;i<=N;i++)
		{
			if(!done[i])
			{
				cout << "Yes" << endl;
				return 0;
			}
		}
		cout << "No" << endl;
		return 0;
	}

	if(cnt6>0||cnt4>1)
	{
		cout << "Yes" << endl;
	}
	else{
		cout << "No" << endl;
	}

	return 0;
}



Measured memory_bytes: 6656
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] s = sc.next().toCharArray();
        char[] t = sc.next().toCharArray();
        int sN = s.length;
        int tN = t.length;

        boolean isReplaced = false;
        for(int i = sN - tN;i >= 0;i--) {
            boolean isPossible = true;
            for(int j = 0;j < tN;j++) {
                if(s[i + j] != '?' && s[i + j] != t[j]) {
                    isPossible = false;
                    break;
                }
            }
            if(isPossible) {
                for(int j = 0;j < tN;j++) s[i + j] = t[j];
                isReplaced = true;
                break;
            }
        }
        
        String ans = isReplaced ? String.valueOf(s).replace('?', 'a') : "UNRESTORABLE";
        System.out.println(ans);
    }
}


Measured memory_bytes: 22740
#include <algorithm>
#include <bitset>
#include <iomanip>
#include <ios>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
using namespace std;

int main()
{
    string a, b, c;
    cin >> a >> b >> c;
    cout << a[0] << b[0] << c[0] << "\n";
}

Measured memory_bytes: 256
import heapq

xs, ys, xt, yt = map(int, input().split())
N = int(input())
XYR = [list(map(int, input().split())) for i in range(N)]
XYR.append([xs, ys, 0])
XYR.append([xt, yt, 0])
L = [[9999999999]*(N+2) for i in range(N+2)]
for i in range(N+2):
    for j in range(i, N+2):
        x1, y1, r1 = XYR[i]
        x2, y2, r2 = XYR[j]
        L[i][j] = L[j][i] = max(((x1-x2)**2+(y1-y2)**2)**0.5-r1-r2, 0.0)


# 計算量 O((E+V)logV)
num = N+2  # グラフのノード数
start = num-2

distance = [float('inf') for i in range(num)]  # 始点から各頂点までの最短距離を格納する
prev = [float('inf') for i in range(num)]  # 最短経路における，その頂点の前の頂点のIDを格納する
distance[start] = 0
q = []  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
heapq.heappush(q, (0, start))  # 始点をpush

while len(q) != 0:
    prov_cost, src = heapq.heappop(q)  # pop

    # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
    if distance[src] < prov_cost:
        continue

    # 他の頂点の探索
    for destination, cost in enumerate(L[src]):
        if distance[destination] > distance[src] + cost:
            distance[destination] = distance[src] + cost  # distの更新
            heapq.heappush(q, (distance[destination], destination))  # キューに新たな仮の距離の情報をpush
            prev[destination] = src  # 前の頂点を記録

print(distance[-1])


Measured memory_bytes: 125148
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int n,k,x,y;
  cin >> n >> k >> x >> y;
  if(n>k){
    int ans = k*x+(n-k)*y;
    cout << ans << endl;
  }else{
    int ans = n*x;
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 256