akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define INF (1<<30)
using namespace std;
struct Edge {
	int a, b, cost;
	Edge() {}
	Edge(int a, int b, int cost) :a(a), b(b), cost(cost) {}
	bool operator < (Edge& o) const{
		return cost < o.cost;
	}
};
int main() {
	cin.tie(0); ios::sync_with_stdio(false);
	int N, M; cin >> N >> M;
	vector<vector<Edge>> G(N + 1);
	vector<Edge> e(M + 1);
	vector<vector<int>> dist(N + 1, vector<int>(N + 1, INF));

	//	initialize
	for (int i = 0; i < M;i++) {
		int a, b, c; cin >> a >> b >> c;
		G[a].emplace_back(Edge(a, b, c));
		G[b].emplace_back(Edge(b, a, c));

		e[i] = Edge(a, b, c);
	}
	// dist[i][j] = i-j間の最短距離値
	for (int i = 1; i <= N; i++) {
		queue<int> q;
		dist[i][i] = 0;
		q.push(i);

		while (!q.empty()) {
			int pre = q.front(); q.pop();
			for (auto o : G[pre]) {
				int next = o.b;
				if (dist[i][pre] + o.cost < dist[i][next]) {
					dist[i][next] = dist[i][pre] + o.cost;
					q.push(next);
				}
			}
		}
	}
	
	int ans = M;
	for (int i = 0; i < M; i++) {
		bool f = false;
		for (int j = 1; j <= N; j++) { if (dist[j][e[i].a] + e[i].cost == dist[j][e[i].b]) f = true; }
		if (f) ans--;
	}

	cout << ans << endl;
	
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string b;
  cin >> b;
  
  if(b=="A")
    cout << "T" << endl;
  if(b=="T")
    cout << "A" << endl;
  if(b=="C")
    cout << "G" << endl;
  if(b=="G")
    cout << "C" << endl;
}

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

using namespace std;

int main() {
  ios::sync_with_stdio(false);

  int n;
  cin >> n;

  vector<int> v(n);

  for (auto& e : v) {
    cin >> e;
  }

  int res = 0;
  for (int i = 0; i < n - 1; i++) {
    for (int j = i + 1; j < n; j++) {
      res += v[i] * v[j];
    }
  }

  cout << res << endl;
}



Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>


using namespace std;
typedef long long int llint;
typedef vector<llint>::iterator it;



void quicker_settings() {
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
}

llint merge(vector<llint> &V, vector<llint> &L, vector<llint> &R) {
	it l = L.begin();
	it r = R.begin();
	llint c = 0;
	for (it v = V.begin(); v != V.end(); ++v) {
		if (r == R.end() || l != L.end() && *l < *r) {
			*v = *l;
			++l;
		}
		else {
			*v = *r;
			c += (L.size() + distance(R.begin(), r) - distance(V.begin(), v));
			++r;
		}
	}
	return c;
}

llint merge_idx(vector<llint> &v) {
	if (v.size() == 1)
		return 0;
	vector<llint> L;
	vector<llint> R;
	L.assign(v.begin(), v.begin() + (v.size() / 2));
	R.assign(v.begin() + (v.size() / 2), v.end());
	llint idx = 0;
	idx += merge_idx(L);
	idx += merge_idx(R);
	idx += merge(v, L, R);
	return idx;
}



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

	vector<llint> v;
	v.resize(n, 0);

	for (llint i = 0; i < n; i++) {
		cin >> v[i];
	}
	llint c = merge_idx(v);

	cout << c << endl;

	return 0;
}

Measured memory_bytes: 7632
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
dp = [[float('inf') for i in range(w)] for j in range(h)]
if s[0][0] == '.':
    dp[0][0] = 0
    total = 0
else:
    dp[0][0] = 1
    total = 1
for i in range(1,w):
    if s[0][i] == '#':
        if s[0][i-1] == '#':
            dp[0][i] = total
        else:
            total += 1
            dp[0][i] = total
    else:
        dp[0][i] = total
if s[0][0] == '.':
    total = 0
else:
    total = 1
for i in range(1,h):
    if s[i][0] == '#':
        if s[i-1][0] == '#':
            dp[i][0] = total
        else:
            total += 1
            dp[i][0] = total
    else:
        dp[i][0] = total
for i in range(1,h):
    for j in range(1,w):
        if s[i][j] == '#':
            if s[i-1][j] == '#' and s[i][j-1] == '#':
                dp[i][j] = min(dp[i-1][j], dp[i][j-1])
            elif s[i-1][j] == '#':
                dp[i][j] = min(dp[i-1][j], dp[i][j-1] + 1)
            elif s[i][j-1] == '#':
                dp[i][j] = min(dp[i][j-1], dp[i-1][j] + 1)
            else:
                dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1)
        else:
            dp[i][j] = min(dp[i-1][j], dp[i][j-1])
print(dp[h-1][w-1])

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


int main() {
  string S, T, U;
  int ball_S, ball_T;
  cin >> S >> T;
  cin >> ball_S >> ball_T;
  cin >> U;
  if (U == S) {
      ball_S--;
  }
  else {
      ball_T--;
  }
  cout << ball_S << " " << ball_T;
  
}



Measured memory_bytes: 256
import java.util.*;
import java.lang.Math;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(true){
            int a=sc.nextInt();
            String in=sc.next();
            int b=sc.nextInt();
            char op[]=in.toCharArray();
            if(op[0]=='+') System.out.println(a+b);
            else if(op[0]=='-') System.out.println(a-b);
            else if(op[0]=='*') System.out.println(a*b);
            else if(op[0]=='/') System.out.println(a/b);
            else break;
        }
    }
}


Measured memory_bytes: 26404
#include<bits/stdc++.h>
#define rep(i,n,m) for(int i = (n); i <(m); i++)
using namespace std;
using ll = long long;
const int max_h = 50;
const int max_w = 50;



int main()
{
    int h, w;
    cin >> h >> w;
    string mass[h + 2];

    mass[0] = mass[h + 1] = "";
    rep(i, 0, w + 2)
    {
        mass[0] += '.';
        mass[h + 1] += '.';
    }

    rep(i, 0, h)
    {
        string s;
        cin >> s;
        mass[i + 1] = '.' + s + '.';
    }

    bool ans = true;
    rep(i, 1, h + 1)
    rep(j, 1, w + 1)
    {
        if (mass[i][j] == '#')
        {
           bool ok = false;
           ok |= mass[i-1][j] == '#';
           ok |= mass[i][j+1] == '#';
           ok |= mass[i+1][j] == '#';
           ok |= mass[i][j-1] == '#';
           ans &= ok;
        }

        if (!ans) break;
    }

    if (ans)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
//AUTHOR:: MOHAMMAD FAISAL
// BEGINNING WITH THE NAME OF ALMIGHTY GOD ALLAH
// Codeforces Beginner Problems
//#include<bits/stdc++.h>
#include<iostream>
#include<bitset>
#include<string>
#include<algorithm>
#include <cctype>
#include<unordered_map>
#include<map>
#include<set>
#include<vector>
#include<utility>
#include<iterator>
using namespace std;
//string password;
int gcd(int a,int b)
{
    if(b==0)
        return a;
    return gcd(b,a%b);
}
bool isVowel(char c)
{
    return c=='a' || c=='e' || c=='i' || c=='o' || c=='u';
}
bool isPrime(long long n)
{
  if (n == 1)
  {
    return false;
  }
  long long int i = 2;
  while (i*i <= n)
  {
      if (n % i == 0)
      {
          return false;
      }
      i += 1;
  }
  return true;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.flush();
    long long a,b;
    cin >> a >> b;
    for(int i=1;i<=b;i++)
        if((a*i)%b==0){
            cout<<a*i<<endl;break;
            
        }
    
    return 0;
}


Measured memory_bytes: 256
N=int(input())
S=[input() for _ in range(N)]

ac=S.count('AC')
wa=S.count('WA')
tle=S.count('TLE')
re=S.count('RE')

print('AC x '+ str(ac))
print('WA x '+ str(wa))
print('TLE x '+ str(tle))
print('RE x '+ str(re))

Measured memory_bytes: 16192
a = []
for i in range(5):
    a.append(int(input()))
k = int(input())
flag = True
for i in range(4):
    for j in range(i+1, 5):
        if abs(a[j]-a[i]) >k:
            flag= False
            break
if flag:
    print('Yay!')
else:
    print(':(')
    

Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
typedef pair<ll,ll> P;
using VP = vector<P>; using VVP = vector<VP>;
using VI = vector<ll>; using VVI = vector<VI>; using VVVI = vector<VVI>;
const int inf=1e9+7;
const ll INF=1LL<<58;
const ll mod=1e9+7;

int main(){
  int i,j;
  int n;
  cin>>n;
  int cnt=0;
  for(i=1;i<n;i++){
    j=n-i;
    if(i<j) cnt++;
  }
  cout<<cnt<<endl;

}


Measured memory_bytes: 256
<?PHP 
$input = trim(fgets(STDIN));
$input2 = explode(' ', trim(fgets(STDIN)));

$i = 0;
$i2 = 0;
foreach ($input2 as $item) {
    if($item % 2 === 0) {
        $i++;
        if ($item % 3 === 0 || $item % 5 === 0){
            $i2++;
        }
    }
}

if ($i === $i2) {
    echo "APPROVED\n";
}else {
    echo "DENIED\n";
}

Measured memory_bytes: 4732
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
n,q = map(int,input().split())
tree = {i : [] for i in range(n)}
for i in range(n-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  tree[a].append(b)
  tree[b].append(a)
score = [0 for _ in range(n)]
for i in range(q):
  p,x = map(int,input().split())
  score[p-1] += x
  
def dfs(parent,node,s):
  for n in tree[node]:
    if n == parent:
      continue
    score[n] += score[node]
    dfs(node,n,s)

dfs(-1,0,0)
  
print(*score)
 

Measured memory_bytes: 248028
#include<iostream>
#define rep(i, n) for(int i = 0; i < (n); ++i)
using namespace std;

int main() {
    char s[3];
    rep(i, 3) cin >> s[i];

    bool exist = false;

    if (s[0] != s[1] || s[1] != s[2] || s[2] != s[0]) exist = true;

    if(exist) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

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


public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.solve(args);
    }

    public void solve(String[] args) {
        MyScanner scanner = new MyScanner();
        int a = scanner.nextInt();
        if (a==1) {
        	System.out.println("Hello World");
        }else {
        	int b = scanner.nextInt();
        	int c = scanner.nextInt();
        	System.out.println(b+c);
        }




    }

    private class MyScanner {
        String[] s;
        int i;
        BufferedReader br;
        String reg = " ";
        MyScanner () {
            s = new String[0];
            i = 0;
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        public String next() {
            try {
                if (i < s.length) return s[i++];
                String line = br.readLine();
                while (line.equals("")) {line = br.readLine();}
                s = line.split(reg, 0);
                i = 0;return s[i++];
            } catch (Exception e) {e.printStackTrace();}
            return null;
        }
        public int nextInt() {
            try {return Integer.parseInt(next());} catch (Exception e) {e.printStackTrace();}
            return -1;
        }
        public double nextDouble() {
            try {return Double.parseDouble(next());} catch (Exception e) {e.printStackTrace();}
            return -1;
        }
        public long nextLong()  {
            try {return Long.parseLong(next());} catch (Exception e) {e.printStackTrace();}
            return -1;
        }
    }
}

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

int main(){
   string S,T,U;
   cin >> S >> T;
   int A,B;
   cin >> A >> B;
   cin >> U;
   if(U==S){
       A--;
   }
   else if(U==T){
       B--;
   }
   cout << A << " " << B << endl;
}

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

int main()
{
	int N;
	string S;
	cin >> N;
	cin >> S;
	int x = 0;
	int ans = 0;
	for (int i = 0; i < N; i++)
	{
		if (S[i]=='I')
		{
			x++;
		}
		else
		{
			x--;
		}

		ans = max(ans, x);
	}
	cout<<ans << endl;
	return 0;
}

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

ll minCost(vector<int> &height, int k){
    const int n = height.size();
    if(n < 2){
        return 0;
    }
    vector<ll> dp(n);
    dp[0] = 0;
    dp[1] = abs(height[0] - height[1]);
    for(int i = 2; i<n;i++){
        dp[i] = INT_MAX;
        for(int j = 1 ; j <= k && i-j>=0 ;j++){
            dp[i] = min( dp[i], dp[i-j] + abs(height[i-j] - height[i]) );
        }
    }
    return dp[n-1];
}
int main(){
    // freopen("in.txt","r",stdin);
    int n,k;
    cin>>n>>k;
    vector<int> arr(n);
    for (int i = 0; i < n; i++){
        cin>>arr[i];
    }
    cout<<minCost(arr,k);
    return 0;
}


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

#define MOD (1000 * 1000 * 1000 + 7)
#define INF (1LL << 60)
#define pb push_back
#define po pop_back
#define fi first
#define se second

typedef long long ll;
typedef long double ld;

string substring(const string &str, int start, int end) {
    string n_str = "";
    for (int i = start; i < str.size() && i < end; ++i)
        n_str += str[i];
    return n_str;
}

ll sum(string str, int i, ll val) {
    if (i >= str.size())
        return 0;
    if (str.size() == 1) {
        return stoll(str);
    }

    string s1 = substring(str, 0, i);
    string s2 = substring(str, i, str.size());

    ll s = 0;
    s += stoll(s1) + stoll(s2);
    s += sum(s2, 1, val + stoll(s1));
    s += sum(str, i + 1, val);
    s += val;

    return s;
}

int main() {
    string str;
    cin >> str;
    cout << sum(str, 1, 0) + stoll(str) << endl;

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
using namespace std;
typedef long long ll;
const int INF=100000000;
const int MOD=1000000007;

int main()
{
 ll n, x=1, y=1;
 cin >> n;
 ll t[n], a[n];
 for(int i=0;i<n;i++){
   cin >> t[i] >> a[i];
 }
 for(int i=0;i<n;i++){
   ll k;
   k=max((x+t[i]-1)/t[i], (y+a[i]-1)/a[i]);
   x=k*t[i];
   y=k*a[i];
 } 
 cout << x+y;
 return 0;
}

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

/* #pragma */
/*
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
*/

/*alias*/
#define F first
#define S second

#define y0 y3487465
#define y1 y8687969
#define j0 j1347829
#define j1 j234892
#define next asdnext
#define prev asdprev
#define itn int

/*template*/
template<class T>inline bool amax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>inline bool amin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }

/* func */
int GCD(int a,int b){return b?GCD(b,a%b):a;}
long long GCD(long long a, long long b){return b ? GCD(b, a%b) : a;}
int LCM(int a, int b){return a * b / GCD(a, b);}
long long LCM(long long a, long long b){return a * b / GCD(a, b);}

/*struct*/
struct aaa {
	aaa() {
		cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20);
	};
}aaaaaaa;

/* const */
const int INF = 1001001001;
const long long LINF = 1001001001001001001ll;
const int MOD = 1e9 + 7; //10^9
const double EPS = 1e-9;
const int dx[] = { 1, 1, 0, -1, -1, -1, 0, 1 }, dy[] = { 0, 1, 1, 1, 0, -1, -1, -1 };
//Counterclockwise from the 6o'clock direction
//Take the x-axis downward and the y-axis right

//#define int ll
//#define int long long

//g++ -std=c++14 -Wall --pedantic-errors -o template template.cpp
//chcp 65001

signed main()
{
	int h, w; cin >> h >> w;
	string s[100];
	for(int i = 0, i_len = h; i < i_len; ++i){
		cin >> s[i];
	}

	for(int i = 0, i_len = h; i < i_len; ++i){
		for(int j = 0, j_len = w; j < j_len; ++j){
			if(s[i][j] == '#')cout << "#";
			else{
				int cnt = 0;
				for (int k = 0; k < 8; ++k)
				{
					int cx = i + dx[k], cy = j + dy[k];
					if(cx < 0 || cx >= h || cy < 0 || cy >= w)continue;
					if(s[cx][cy] == '#')++cnt;
				}
				cout << cnt;
			}
		}
		cout << endl;
	}
	return 0;
}

Measured memory_bytes: 256
using System ; 

namespace Program{
 class Program{
  static void Main(string []args){
   string []buff = Console.ReadLine().Split(' ');
    
   int N = int.Parse(buff[0] ) ;
   
   int Q = int.Parse(buff[1]) ;
    
   string S = Console.ReadLine() ; 
    
   int count = 0 ;
    
   for(int i = 0 ; i < S.Length - 1; i++){
     if( S[i] == 'A'){
       if( S[i+1] == 'C'){
         count++; 
       }else if( S[i+1] == 'A'){
         i--;
       }
       i++;
     }
   }
   int []L = new int[N + 1];
   int []R = new int[N + 1]; 
   if( count > 0 ){
      for(int i = 2 ; i <= N; i++){
        if( S[i-1 - 1] == 'A' && S[i -1 ] == 'C' ){
          L[i] = L[i-1] + 1;
        }
        else{
          L[i] = L[i-1]; 
        }
        
        if( S[S.Length - i ] == 'A' && S[S.Length - i + 1] == 'C' ){
          R[i] = R[i-1] + 1;
        }
        else{
          R[i] = R[i-1]; 
        }
        
      }     
   }
  for(int i = 0 ; i < Q ; i++){
    buff = Console.ReadLine().Split(' ');
    int left = int.Parse(buff[0]) ;
    int right = int.Parse(buff[1] ) ; 
    Console.WriteLine( count - L[left] - R[N-right+1] ) ;
  }
  }
 }
}

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


int main(void){
  int k; cin >> k;
  ll sum = 0;
  for(int a = 1; a <= k; a++){
    for(int b = 1; b <= k; b++){
      for(int c = 1; c <= k; c++){
        sum += gcd(a,gcd(b,c));
      }
    }
  }
  cout << sum << endl;
  return 0;
}


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

int n;
int d[100005];

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> d[i];
	vector<int> idx;
	for (int i = 1; i <= n; i++) {
		if (d[i] == i) idx.push_back(i);
	}
	int ans = 0;
	int i = 0, start = 0;
	while (i < idx.size()) {
		int cnt = 0;
		while (i < idx.size() && (i == start || idx[i] - idx[i - 1] == 1)) {
			i++; cnt++;
		}
		ans += (cnt + 1) / 2;
		start = i;
	}
	cout << ans << endl;
}

Measured memory_bytes: 1276
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vs = vector<string>;
using pll = pair<ll, ll>;
using vp = vector<pll>;
#define rep(i, n) for(ll i = 0; i < (n); i++)
#define repr(i, a, b) for(ll i = (a); i < (b); i++)
#define ALL(a) (a).begin(), (a).end()
#define SZ(x) ((ll)(x).size())
const ll MOD = 1000000007;
const ll INF = 100000000000000000LL;
inline ll GCD(ll a, ll b){ return b?GCD(b, a % b):a; }
inline ll LCM(ll a, ll b){ return a/GCD(a, b)*b; }
inline ll powint(unsigned long long x, ll y){ ll r=1; while(y){ if(y&1) r*=x; x*=x; y>>=1; } return r; }
inline ll powmod(ll x, ll y, ll m = MOD){ ll r=1; while(y){ if(y&1) r*=x; x*=x; r%=m; x%=m; y>>=1; } return r; }
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; }
#ifdef OJ_LOCAL
#include "dump.hpp"
#else
#define dump(...) ((void)0)
#endif

int main(){
    cin.tie(0); ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    ll h, w;
    cin >> h >> w;
    vvll a(h, vll(w, 0));
    rep(i, h){
        rep(j, w){
            cin >> a[i][j];
            a[i][j] %= 2;
        }
    }
    vvll ans;
    rep(i, h){
        rep(j, w-1){
            if(a[i][j] == 1){
                ans.emplace_back(vll({i+1, j+1, i+1, j+2}));
                a[i][j]--;
                a[i][j+1]++;
                a[i][j+1] %= 2;
            }
        }
    }
    rep(i, h-1){
        if(a[i][w-1] == 1){
            ans.emplace_back(vll({i+1, w, i+2, w}));
            a[i][w-1]--;
            a[i+1][w-1]++;
            a[i+1][w-1] %= 2;
        }
    }
    cout << SZ(ans) << endl;
    rep(i, SZ(ans)){
        rep(j, SZ(ans[i])){
            cout << ans[i][j] << " \n"[j+1==SZ(ans[i])];
        }
    }
    return 0;
}

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

int main() {
  int N,M;
  cin >> N >> M;
  map<int,int> mp;
  for(int i=0;i<N;i++){
    int k;
    cin >> k;
    for(int j=0;j<k;j++){
      int a;
      cin >> a;
      mp[a-1]++;
    }
  }
  int sum=0;
  for(int i=0;i<M;i++){
    if(mp[i]==N)sum++;
  }
  cout << sum;
}
       

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef pair<int,int>P;
#define F first
#define S second

int dp[1111];
int a,b,n,sum,sum2;
vector<P>v;

signed main(){
  while(cin>>n,n){
    sum=sum2=0;
    v.clear();
    r(i,n){
      cin>>a>>b;
      v.push_back(P(a,b));
    }
    sort(v.begin(),v.end());
    r(i,n-1)sum+=v[i].F;
    r(i,n)sum2+=v[i].S;
    if(sum>=v[n-1].F){
      cout<<sum+sum2+v[n-1].F<<endl;
      continue;
    }
    memset(dp,0,sizeof(dp));
    dp[0]=1;
    for(int i=0;i<n-1;i++){
      for(int j=1100;j>=0;j--)if(dp[j]){
        if(j+v[i].F<1001)dp[j+v[i].F]=1;
        if(j+v[i].F+v[i].S<1001)dp[j+v[i].F+v[i].S]=1;
      }
    }
    for(int i=v[n-1].F;i>=0;i--){
      if(!dp[i])continue;
      cout<<v[n-1].F-i+v[n-1].F+sum+sum2<<endl;
      break;
    }
  }
}


Measured memory_bytes: 3124
/*{{{*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<iostream>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include<bitset>
#include<vector>
#include<limits.h>
#include<assert.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define FOR(I, A, B) for (int I = (A); I <= (B); ++I)
#define FORS(I, S) for (int I = 0; S[I]; ++I)
#define RS(X) scanf("%s", (X))
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define CASET int ___T; scanf("%d", &___T); for(int cs=1;cs<=___T;cs++)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<PII> VPII;
typedef pair<LL,LL> PLL;
typedef vector<PLL> VPLL;
template<class T> void _R(T &x) { cin >> x; }
void _R(int &x) { scanf("%d", &x); }
void _R(LL &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); }
template<class T> void _W(const T &x) { cout << x; }
void _W(const int &x) { printf("%d", x); }
void _W(const LL &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template<class T,class U> void _W(const pair<T,U> &x) {_W(x.F); putchar(' '); _W(x.S);}
template<class T> void _W(const vector<T> &x) { for (auto i = x.begin(); i != x.end(); _W(*i++)) if (i != x.cbegin()) putchar(' '); }
void W() {}
template<class T, class... U> void W(const T &head, const U &... tail) { _W(head); putchar(sizeof...(tail) ? ' ' : '\n'); W(tail...); }
#ifdef HOME
 #define DEBUG(...) {printf("# ");printf(__VA_ARGS__);puts("");}
#else
 #define DEBUG(...)
#endif
int MOD = 1e9+7;
void ADD(LL& x,LL v){x=(x+v)%MOD;if(x<0)x+=MOD;}
/*}}}*/
const int SIZE = 1e6+10;
const int INF = 1000000000;
int main(){
    int n,k,s;
    R(n,k,s);
    VI an(n);
    if(s<INF){
        REP(i,k)an[i]=s;
        REPP(i,k,n)an[i]=INF;
    }
    else{
        REP(i,k)an[i]=s;
        REPP(i,k,n)an[i]=1;
    }
    W(an);
    return 0;
}


Measured memory_bytes: 1664
#include<iostream>
#include<bits/stdc++.h>
#include<algorithm>
typedef long long int ll;
typedef unsigned long long int ull;
using namespace std;
# define my_sizeof(type) ((char *)(&type+1)-(char*)(&type)) 
#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define loop(i,a,b) for(ull i=a;i<b;i++)
#define test() ull t;cin>>t;while(t--)
#define pb push_back
#define mkp make_pair
#define nl cout<<endl
#define MOD 1000000007
#define trace(s,a) cout<<s<<a,nl

int main(){
	string s;
    cin>>s;

    if(s[0] == s[1] || s[1] == s[2] || s[2] == s[3]){
    	cout<<"Bad"<<endl;
    }else{
    	cout<<"Good";
    	nl;
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull usigned long long
#define two(n) 1<<n
#define l(v) (int)v.size()
#define p_b push_back
#define m_p make_pair
const int pi=acos(-1.0);
const int int_max=1e9;
const long long ll_max=1e18;
int n,a[105];
int main()
{
	cin>>n;
	for(int i=0;i<n-1;i++)
		cin>>a[i];
	int ans=0;
	if(n==2)
	{
		cout<<a[0]*2;
		return 0;
	}
	ans+=a[0];
	ans+=(a[0]>a[1]?a[1]:a[0]);
	for(int i=1;i<n-1;i++)
		if(a[i]>a[i+1]&&i!=n-2)
			ans+=a[i+1];
		else
			ans+=a[i];
	cout<<ans;
	return 0;
}

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

void input(){
    int n; cin >> n;
    vector<int>a(n);
    multiset<int>s;
    f(i, n) {cin >> a[i];s.insert(a[i]);}
    f(i, n){
        s.erase(s.find(a[i]));
        cout << *s.rbegin() << "\n";
        s.insert(a[i]);
    }
}
int main()
{
 input();
 return 0;
}


Measured memory_bytes: 11776
#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
typedef long long ll;
typedef long double lb;
#define int long long
#define double long double
typedef pair<int,int> P;
const int MOD = 1000000007;
const ll INF = 1e16;
const double EPS = 1e-10;
const double PI = 3.141592653589793;
template<class T> inline bool chmin(T& a, T b){if(a>b){a = b;return 1;}return 0;}
template<class T> inline bool chmax(T& a, T b){if(a<b){a = b;return 1;}return 0;}
const pair<int,int> fd[] = {make_pair(1,0),make_pair(-1,0),make_pair(0,1),make_pair(0,-1)}; 


////////////////////////////////////////////////////////////////////

int h,n,a[1100],b[1100];
int dp[21000];
signed main(){
  cin>>h>>n;
  rep(i,n)cin>>a[i]>>b[i];
  rep(i,21000)dp[i] = INF;dp[0] = 0;
  repd(i,1,21000){
    rep(j,n){
      if(i-a[j] >= 0)chmin(dp[i],dp[i-a[j]]+b[j]);
    }
  }
  int ans = INF;
  repd(i,h,21000)chmin(ans, dp[i]);
  cout << ans << endl;
}



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

int main()
{
	int d, t, s;
	cin >> d >> t >> s;

	int r = d / s;
	if (d % s != 0) {
		r++;
	}

	if (r <= t) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}


	return 0;
}

Measured memory_bytes: 3636
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <numeric>
#include <limits.h>
#include <cmath>

int main()
{
    int A, B, T;
    std::cin >> A >> B >> T;
    std::cout << (T / A) * B << std::endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
    string s; cin >> s;
    int k; cin >> k;
    int n = s.size();
    for (int i = 0; i < n; i++) {
        if (s[i] != 'a') {
            int t = 'z' - s[i] + 1;
            if (t <= k) {
                s[i] = 'a';
                k -= t;
            }
        }
    }
    if (k > 0) {
        k %= 26;
        s.back() += k;
    }
    cout << s << endl;
    return 0;
}

Measured memory_bytes: 512
a = []
c = [[0]*3 for i in range(3)]
for i in range(3):
    tmp = list(map(int,input().split()))
    a.append(tmp)
n = int(input())
b = []
for i in range(n):
    b.append(int(input()))
for i in b:
    for j in range(3):
        for k in range(3):
            if a[j][k] == i:
                c[j][k] = 1
if (c[0][0] == 1 and c[1][1] == 1 and c[2][2] == 1
    or c[2][0] == 1 and c[1][1] == 1 and c[0][2] == 1
    or c[0][0] == 1 and c[0][1] == 1 and c[0][2] == 1
    or c[1][0] == 1 and c[1][1] == 1 and c[1][2] == 1
    or c[2][0] == 1 and c[2][1] == 1 and c[2][2] == 1
    or c[0][0] == 1 and c[1][0] == 1 and c[2][0] == 1
    or c[0][1] == 1 and c[1][1] == 1 and c[2][1] == 1
    or c[0][2] == 1 and c[1][2] == 1 and c[2][2] == 1):
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstdlib>
#include<queue>
#include<set>
#include<cstdio>

using namespace std;

#define ll long long
#define rep(i, n) for(int i = 0; i < n; i++)
#define P pair<int, int>

typedef vector<int> vec;
typedef vector<vec> mat;

const ll mod = 1000000007;

int main(){
    ll n, x, m;
    cin >> n >> x >> m;
    ll modn[m];
    fill(modn, modn + m, -1);
    ll a = x % m;
    modn[a] = 1;
    ll loop = 0;
    ll cnt = 2;
    while(cnt <= n){
        a = (a * a) % m;
        if(modn[a] != -1){
            loop = cnt - modn[a];
            break;
        }else{
            modn[a] = cnt;
            cnt++;
        }
    }

    ll ans = 0;
    if(loop == 0){
        rep(i, m){
            if(modn[i] == -1) continue;
            else ans += i;
        }
    }else{
        ll loop_num = (n - modn[a]) / loop;
        ll p = (n - modn[a]) % loop;
        rep(i, m){
            if(modn[i] == -1) continue;
            if(modn[a] > modn[i]) ans += i;
            else{
                if(modn[a] + p >= modn[i]){
                    ans += i * (loop_num + 1);
                }else{
                    ans += i * loop_num;
                }
            }
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 4412
#include <bits/stdc++.h>
#include <ext/rope>
using namespace std;
using namespace __gnu_cxx;

using ci = const int;
using ld = long double;
using llint = long long;
using ullint = unsigned long long;
using pii = pair <int,int>;
using pcc = pair <char,char>;
using pss = pair <string,string>;
using vi = vector <int>;
using vb = vector <bool>;
using vii = vi::iterator;

#define INF (1<<30)
#define MOD 1000000007
#define mt make_tuple
#define all(c) c.begin(), c.end()
#define ms(name,val) memset(name, val, sizeof name)
#define np nullptr
// inline functions



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

    int a, b, c, d, e, k;
    cin >> a >> b >> c >> d >> e >> k;

    if (e-a > k)
        cout << ":(";
    else
        cout << "Yay!";


    return 0;
}

Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))
cnt = 0
# dp = [0]*N
# for i in range(N-1):
#     t = A[i]
#     if t > 200000:
#         continue
#     for j in range(i+t+1, N):
#         if j-i == t+A[j]:
#             cnt += 1
# print(cnt)

# i<j
# j-i = A[i]+A[j]
# j-A[j] = i+A[i]
# j+A[j] = i-A[i]
MAX = 2*10**5

dpL = [0]*(MAX)
dpR = [0]*(MAX)
for i in range(N):
    num = A[i]
    if num > 200000:
        continue   
    if i+num < MAX:
        dpL[i+num] += 1
    if i >= num:
        dpR[i-num] += 1

for i in range(MAX):
    l = dpL[i]
    r = dpR[i]
    cnt += l*r

print(cnt)


Measured memory_bytes: 92948
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define SZ(x) ((int)(x).size())
#define rep(i,n) for(int i=0;i<(n);++i)
#define fore(i,a) for(auto &i:a)
#define min(...) min({__VA_ARGS__})
#define max(...) max({__VA_ARGS__})
#define Yes cout << "Yes" << endl;
#define No cout << "No" << endl;
#define answer cout << ans << endl;
signed _main(); signed main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> using v = vector<T>;
template<class T> using vv = vector<v<T>>;
const int MOD=1e9+7;
const long long INF = 1LL << 60;

signed _main(){
  // 入力: H × W のグリッド
  int H, W, K, ans=INF,res; cin >> H >> W >> K;
  vector<vector<int> > a(H, vector<int>(W));
  for (int i = 0; i < H; ++i){
    for (int j = 0; j < W; ++j){
      char chara; cin >> chara;
      a[i][j]=chara-'0';
    }
  }
  // 二次元累積和
  vector<vector<int> > s(H+1, vector<int>(W+1, 0));
  for (int i = 0; i < H; ++i)for (int j = 0; j < W; ++j) s[i+1][j+1] = s[i][j+1] + s[i+1][j] - s[i][j] + a[i][j];

  for (int bit = 0; bit < (1 << (H-1)); ++bit) {
    res=0;
    v<int> ver;
    ver.push_back(0);
    for (int i = 0; i < H-1; ++i) {
      if (bit & (1 << i)){
        ver.push_back(i+1);
        res++;
      }
    }
    ver.push_back(H);
    int x1, x2, y1, y2;
    y1=0;
    for(int y=1;y<=W;y++){
      y2=y;
      int cnt=0;
      rep(i,SZ(ver)-1){
        x1=ver[i],x2=ver[i+1];
        if(s[x2][y2] - s[x1][y2] - s[x2][y1] + s[x1][y1]<=K);
        else{
          if(s[x2][y2-1] - s[x1][y2-1] - s[x2][y1] + s[x1][y1]>K) res=INF;
          y1=y-1;
          res++;
        }
      }
    }
/*
    cout << "ver" << endl;
    fore(i,ver) cout << i << endl;
    cout << "res " << res << endl;
*/
    chmin(ans,res);
  }
  answer
  return 0;
}


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

using namespace std;
using ll = long long;
using P = pair<int, int>;
const string YES = "Yes";
const string NO = "No";

void solve(long N, vector<long> a) {
  long count2(0);
  long count4(0);
  REP(i, N)
    switch (a[i] % 4) {
    case 0:
      count4++;
      break;
    case 2:
      count2++;
      break;
    }
  cout << ((count4 * 2 + count2 >= N) || (count4 * 2 + 1 >= N && count2 == 0) ? YES : NO) << endl;
}

int main(){
  // int 3E4  long 2E9  ll 9E18
  cin.tie(0);
  ios::sync_with_stdio(false);

  long N;
  cin >> N;
  vector<long> a(N);
  REP(i, N)
    cin >> a[i];

  solve(N, move(a));

  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#include <math.h>
#define _GLIBCXX_DEBUG
using namespace std;
int main() {
  
  int N;cin>>N;
  
  if(N<1000){
    cout<<"ABC"<<endl;
  }
  else{
    cout<<"ABD"<<endl;
  }
}

Measured memory_bytes: 3588
// ADITYA JAIN

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

#define f first
#define s second
#define pb push_back
#define all(c) c.begin(),c.end()

#define gi(x) scanf("%d", &x)
#define pi(x) printf("%d", x)
#define gl(x) scanf("%lld", &x)
#define pl(x) printf("%lld", x)
#define nl printf("\n")
#define sp printf(" ")

typedef long long int lld;
typedef long double ldb;

#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
    template <typename Arg1>
    void __f(const char* name, Arg1&& arg1){
        cerr << name << " : " << arg1 << std::endl;
    }
    template <typename Arg1, typename... Args>
    void __f(const char* names, Arg1&& arg1, Args&&... args){
        const char* comma = strchr(names + 1, ','); cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
    }
#else
#define trace(...)
#endif


main(){
    lld n;
    cin >> n;
    cout << n/3 << endl;
}


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

#define INF 1000010000
#define nl '\n'
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pdd pair<double,double>
#define all(c) (c).begin(), (c).end()
#define SORT(c) sort(all(c))
#define sz(c) (c).size()
#define rep(i,n) for( int i = 0; i < n; ++i )
#define repi(i,n) for( int i = 1 ; i <= n; ++i )
#define repn(i,n) for( int i = n - 1 ; i >= 0 ; --i )
#define repf(j,i,n) for( int j = i ; j < n ; ++j )
#define die(s) {std::cout << s << nl;}
#define dier(s) {std::cout << s; return 0;}
#define vi vector<int>
typedef long long ll;

using namespace std;


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.precision(0); 

	int n;
	cin >> n;
	
	vi a(n);
	
	rep(i , n){
		cin >> a[i];
	}
	
	vi b(n);
	
	int l = 0 , r = n - 1;
	
	repn(i , n){
		if((n - i + 1) & 1){
			b[l] = a[i];
			++l;
		}else{
			b[r] = a[i];
			--r;
		}
	}
	
	reverse(all(b));
	
	rep(i , n){
		cout << b[i] << " ";
	}

	return 0;
}

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

using namespace std;

typedef long double ld;

const int MAX_N = 3e3 + 5;

int n;

long double p[MAX_N];

long double dp[MAX_N][MAX_N];

int main() {
  // dp[i][j] = the probability to get j heads using first i coins
  // dp[i][j] = the probability to take coin j + not to take it
  ld ans;
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> p[i];
  }
  dp[0][0] = 1.0;
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j <= n; ++j) {
      if (j == 0) {
        dp[i][j] = (1.0 * dp[i - 1][j] * (1.0 - p[i]));
      } else {
        dp[i][j] = (1.0 * dp[i - 1][j] * (1.0 - p[i])) + (1.0 * dp[i - 1][j - 1] * p[i]);
      }
    }
  }
  ans = 0.0;
  for (int i = 1 + n / 2; i <= n; ++i) {
    ans += dp[n][i];
  }
  cout << setprecision(10) << ans << "\n";
  return 0;
}


Measured memory_bytes: 141184
#include<stdio.h>
int main(void){
  unsigned int i,num,outs,flg;
  while(scanf("%u",&num) && num){
    flg=0;
    for(i=0;i<10;i++){
      outs=(num >> (27-3*i))&7;
      if(outs==0 && flg==0) continue;
      flg=1;
      switch(outs){
      case 5:
      case 6:
      case 7:
	outs++;
      case 4:
	outs++;
      }
      printf("%u",outs);
    }
    putchar('\n');
  }
  return 0;
}

Measured memory_bytes: 0
d, g = map(int, input().split())
ps = [0]*d
cs = [0]*d

for i in range(d):
  p, c = map(int, input().split())
  ps[i] = p
  cs[i] = c

min_count = sum(ps)
for i in range(2**d-1):
  point = 0
  count = 0
  max_other_j = -1
  for j in range(d):
    if (i >> j) & 1:
      point += (j+1)*100*ps[j] + cs[j]
      count += ps[j]
    else:
      max_other_j = max(max_other_j, j)
  if point < g:
    if max_other_j < 0:
      continue
    else:
      if (g - point)%((max_other_j+1)*100) == 0:
        other_count = (g - point)//((max_other_j+1)*100)
      else:
        other_count = (g - point)//((max_other_j+1)*100)+1
      if other_count >= ps[max_other_j]:
        continue
      else:
        count += other_count
  if count <= min_count:
    min_count = count
  
print(min_count)

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

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

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

    sort(a, a + n);

    long long ans = 1;
    int flag = 0;
    
    if(n % 2 == 1){
        for(int i = 0; i < n; i++){
            if(i == 0){
                if(a[i] == 0){
                    continue;
                }else{
                    flag = 2;
                    break;
                }
            }else if(i % 2 == 1){
                if(i + 1 != a[i]){
                    flag = 2;
                    break;
                }
            }else{
                if(i == a[i]){
                    ans *= 2;
                }else{
                    flag = 2;
                    break;
                }
            }
            ans %= 1000000007;
        }
    }else{
        for(int i = 0; i < n; i++){
            if(i % 2 == 0){
                if(i + 1 != a[i]){
                    flag = 2;
                    break;
                }
            }else{
                if(i == a[i]){
                    ans *= 2;
                    ans %= 1000000007;
                }else{
                    flag = 2;
                    break;
                }
            }
        }
    }

    if(flag == 2){
        cout << 0 << endl;
    }else{
        cout << ans << endl;
    }
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define  rep(i, n) for(int i = 0; i < n; i++) 
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  INF 1LL << 60
typedef long long int LL;
typedef long long int ll;
#define pll pair<ll, ll>
#define F first
#define S second
const int MOD = 1000000007;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return true; } return false; }
//sort(all(x))とするとソートできるよ
// 10^x は pow(10,(x)) 
// 任意のlogは　対数の底の変換を使う    log(N) / log(任意の底)

int main(){
    LL N;cin >> N;
    vector<LL> L(N,0);
    rep(i,N){
        LL a;
        cin >> a ;
        L[a]++;
    }
    bool ok = true;
    if(N % 2 != 0){
        if(L[0] != 1)ok = false;
        for(int i = 2;i<N;i += 2)if(L[i] != 2)ok = false;
    }
    if(N % 2 == 0){
        for(int i = 1;i<N;i += 2)if(L[i] != 2)ok = false;
    }
    if(ok){
        LL ans = 1;
        LL lim = N/2;
        rep(i,lim){
            ans *= 2;
            ans %= MOD;
        }
        cout << ans << endl;
    }
    else cout << 0 << endl;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define mp make_pair
typedef pair<int,int> pii;
typedef priority_queue<int,vector<int>,greater<int> > small_heap;
typedef priority_queue<int> big_heap;
pii food[3009];
int maxv[3009],dp[3009][3009];
int n,t;
int main()
{
    scanf("%d%d",&n,&t);
    for(int i=1;i<=n;i++)scanf("%d%d",&food[i].first,&food[i].second);
    sort(food+1,food+n+1);
    for(int i=n;i>=1;i--)maxv[i]=max(maxv[i+1],food[i].second);
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=t-1;j++)
        {
            dp[i][j]=dp[i-1][j];
            if(j>=food[i].first)
                dp[i][j]=max(dp[i][j],dp[i-1][j-food[i].first]+food[i].second);
        }
        ans=max(ans,dp[i][t-1]+maxv[i+1]);
    }
    printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 35584
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define pb push_back
#define vec vector<int>
#define fo(i, n) for (int i = 0; i < n; i++)
#define foo(i, a, b) for (int i = a; i < b; i++)
#define mp make_pair
#define deb(x) cout << #x << "-->" << x << endl;
#define deb1a(v)                  \
    cout << #v << "--->" << endl; \
    for (auto it : v)             \
    {                             \
        cout << it << " ";        \
    }                             \
    cout << endl;
#define deb2a(v)                  \
    cout << #v << "--->" << endl; \
    for (auto it : v)             \
    {                             \
        for (auto it1 : it)       \
        {                         \
            cout << it1 << " ";   \
        }                         \
        cout << endl;             \
    }
    #define mod 998244353
 
#define fi first
#define se second

int32_t main() 
{
  int n,r;
  cin>>n>>r;
  if(n>=10)
  cout<<r;
  else{
      cout << r + 100 * (10 - n);
  }
} 

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)n;i++)
using Graph = vector<vector<int> >;
using GraphC = vector<vector<char> >;
typedef pair<int, int> P;
typedef int64_t ll;
const int MAX_N = 10000;
const int INF = 1000000000;


int main() {
	string S;
	cin >> S;
	int n = S.size();
	vector<int> a(n + 1);
	for (int i = 0; i < S.size(); i++)
	{
		if (S.at(i) == '<') {
			a[i + 1] = max(a[i + 1], a[i] + 1);
		}
	}
	for (int i = n-1; i >=0 ; i--)
	{
		if (S.at(i)=='>')
		{
			a[i] = max(a[i], a[i + 1] + 1);
		}
	}
	ll ans = 0;
	for (int i = 0; i <= n; i++)
	{
		ans += a.at(i);
	}
	cout << ans << endl;
}


Measured memory_bytes: 5872
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;


/*void printvec(vector<int> v) {
	int a = v.size();
	for (int i = 0; i < a; i++) {
		printf("%d ", v[i]);
	}
	printf("\n");
}*/


int main(){
	int a,b,c;
	cin >> a >> b;
	if (a > b) {
		c = a;
		a = b;
		b = c;
	}
	for(int i=0;i<b;i++)
		cout << a;
	cout<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

int main(){
 int N,M;
 std::cin>>N>>M;
 int* A=new int[M];
 for(int i=0;i<M;i++){
  std::cin>>A[i];
 }
 
 int sum=0;
 for(int i=0;i<M;i++){
  sum+=A[i];
 }
 int ans=N-sum;
 if(ans<0){
  ans=-1;
 }
 std::cout<<ans<<std::endl;
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
typedef long long ll;
#define MOD 1000000007
using namespace std;
int main() {
    string s, t;
    cin >> s >> t;
    int ans = 0;
    for(int i = 0; i < s.size(); i++) {
        ans += s[i] != t[i];
    }
    cout << ans << endl;
}

Measured memory_bytes: 3924
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>
#include<set>
using namespace std;
typedef pair<int,int> P;

int main(){
    int N;
    int C[505],S[505],F[505];
    cin>>N;
    for(int i=1;i<N;i++){
        cin>>C[i]>>S[i]>>F[i];
    }
    for(int j=1;j<N;j++){
        int ans=0;
        for(int i=j;i<N;i++){//i to i+1の過程を処理。ループの終わりでi+1に到着する時刻を返す。
            if(ans<S[i]){
                ans=S[i];
            }else{
                int tmp=ans%F[i];
                if(tmp!=0){
                    ans = ans - tmp + F[i];
                }
            }
            ans+=C[i];
        }
        cout<< ans <<endl;
    }
    cout<<0<<endl;
    return 0;
}



Measured memory_bytes: 256
a,b,c,d,e=map(int,input().split())
f=a%b
g=a%d
if f==0:
    h=c*(a//b)
else:
    h=c*((a//b)+1)
if g==0:
    i=e*(a//d)
else:
    i=e*((a//d)+1)

print(min(h,i))


Measured memory_bytes: 5596
#include<iostream>
#include<map>
#include<algorithm>
using namespace std;

int main(){

	map<int ,int> ma;
	int a,L;

	while(1){

		ma.clear();
		cin>>a>>L;
		if(a==0&&L==0) break;

		int ind=0;
		ma.insert(map<int, int>::value_type(a,ind));
		ind++;

		while(1){
			int AL[10];
			int ii=0;
			while(ii<L){
				AL[ii]=a%10;
				a/=10;
				ii++;
			}
			sort(AL,AL+L);
			int maxn=0,minn=0;
			for(int i=0;i<L;i++){
				minn*=10;
				minn+=AL[i];
			}
			for(int i=L-1;i>=0;i--){
				maxn*=10;
				maxn+=AL[i];
			}
			a=maxn-minn;
			if(ma.find(a)!=ma.end()){
				break;
			}
			else{
				ma.insert(map<int, int>::value_type(a,ind));
				ind++;
			}
		}
		cout<<ma[a]<<" "<<a<<" "<<ind-ma[a]<<endl;
	}
}

Measured memory_bytes: 1212
from collections import Counter

H, W, N = [int(v) for v in input().split()]

square_list = []
for i in range(N):
    a, b = [int(v) for v in input().split()]
    for p in range(3):
        for q in range(3):
            if 1 <= a-p <= H-2 and 1 <= b - q <= W-2:
                square_list.append((a - p, b - q))

square_cnt = Counter(square_list)
ans = {i: 0 for i in range(10)}
ans[0] = (H-2) * (W-2) - len(square_cnt)
for cnt in square_cnt.values():
    ans[cnt] += 1

for k in sorted(ans.keys()):
    print(ans[k])

Measured memory_bytes: 198524
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#include<iomanip>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-7
#define mp(a1,a2) make_pair(a1,a2)
typedef long long ll;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
int main(){
	ll A,B;
	scan(A);scan(B);
	ll ans=0;
	for(ll keta=1;keta<=45;keta++){
		if(keta==1){
			ll kosu=0;
			for(int i=A%4;i<=B%4+4;i++){
				kosu+=i%2;
			}
			kosu%=2;
			ans+=kosu;
			continue;
		}
		ll onebegin=min(A%(1LL<<keta),B%(1LL<<keta)),oneend=max(A%(1LL<<keta),B%(1LL<<keta));
		ll junkosu;
		if(oneend<(1LL<<(keta-1))){
			junkosu=0;
		}
		else{
			junkosu=(oneend-max(onebegin,(1LL<<(keta-1)))+7)%2;
		}
		if(A%(1LL<<keta)<=B%(1LL<<keta)){
			//printf("A:%lld B:%lld keta:%lld begin:%lld end:%lld junkosu:%lld\n",A%(1LL<<keta),B%(1LL<<keta),keta,onebegin,oneend,junkosu);
			ans+=junkosu*(1LL<<(keta-1));
		}
		else{
			ll kosu=0;
			kosu=((1LL<<(keta-1))-junkosu+(onebegin>=(1LL<<(keta-1)))+(oneend>=(1LL<<(keta-1)))+8)%2;
			ans+=kosu*(1LL<<(keta-1));
			//printf("A:%lld B:%lld keta:%lld begin:%lld end:%lld junkosu:%lld kosu:%lld\n",A%(1LL<<keta),B%(1LL<<keta),keta,onebegin,oneend,junkosu,kosu);
		}
	}
	prin(ans);
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <algorithm>
using namespace std;
using ll = long long;
 
int v[1000010];
int main() {
	int s;
	scanf("%d", &s);
	for (int i = 1; true; i++) {
		if (v[s]) {
			printf("%d\n", i);
			return 0;
		}
		v[s] = true;
		if (s & 1)
			s = s * 3 + 1;
		else
			s = s / 2;
	}
}

Measured memory_bytes: 128