akhauriyash/Code-Regression huggingface dataset:
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = Integer.parseInt(sc.nextLine());
		String s = sc.nextLine();
		String[] spl = s.split(" ");
		int[] p = new int[N];
		for(int i = 0;i < N;i++){
			p[i] = Integer.parseInt(spl[i]);
		}
		sc.close();

		int cnt = 0;
		for(int i = 1;i < N - 1;i++){
			if((p[i - 1] < p[i] &&  p[i] < p[i + 1]) ||
					p[i - 1] > p[i] &&  p[i] > p[i + 1]){
				cnt++;
			}
		}
		System.out.println(cnt);
	}
}

Measured memory_bytes: 23636
import fractions

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

cc = (B//C)-((A-1)//C)
dd = (B//D)-((A-1)//D)

x= (C * D // fractions.gcd(C, D))
ee = (B//x)-((A-1)//x)

ans = (B-A+1)-(cc + dd - ee)
print(int(ans))

Measured memory_bytes: 5048
#include <iostream>
#include <cstdlib>
#include <cstdio>
#define N 2000011
#define MAX 998244353
#define int long long
using namespace std;
int n,m,inv[N],fac[N],ans;
int ksm(int x,int y){
	int ret=1;
	while(y){
		if(y&1) ret=ret*x%MAX;
		x=x*x%MAX;
		y>>=1;
	}
	return ret;
}
int C(int n,int m){
	return fac[n]*inv[m]%MAX*inv[n-m]%MAX;
}
void init(){
	inv[0]=inv[1]=1;fac[0]=1;
	for(int i=2;i<N-2;i++) inv[i]=(MAX-MAX/i)*inv[MAX%i]%MAX;
	for(int i=1;i<N-2;i++) fac[i]=fac[i-1]*i%MAX;
	for(int i=2;i<N-2;i++) inv[i]=(inv[i-1]*inv[i])%MAX;
}
signed main(){
	scanf("%lld%lld",&n,&m);
	if(n<m) swap(n,m);
	init();
	for(int i=1;i<=m;i++){
		ans+=C(i*2,i)*C(n-i+m-i,n-i)%MAX;
		ans%=MAX;
	}
	ans=ans*ksm(2,MAX-2)%MAX;
	ans=ans*ksm(C(n+m,m),MAX-2)%MAX;
	ans=(ans+n)%MAX;
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 31616
// Problem : B - Trick or Treat
// Contest : AtCoder - AtCoder Beginner Contest 166
// URL : https://atcoder.jp/contests/abc166/tasks/abc166_b
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>

#define FIO ios_base::sync_with_stdio(0); cin.tie(0);
#define T() int tt; cin >> tt; rep1(qq,1,tt)
#define rep(i,start,lim) for(int i=start;i<lim;i++)
#define rep1(i,start,lim) for(int i=start; i<=lim; ++i)
#define repd(i,start,lim) for(int i=start;i>=lim;i--)
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define br cout<<"\n"
#define MOD (1000000007LL)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define eps (1e-6)
#define what_is(x) cerr << #x << " is " << x << "\n";
#define int long long int
#define infll 9e18
#define inf 1e12

#define lnode (2 * node + 1)
#define rnode (2 * node + 2)

using namespace std;

typedef pair<int, int> pii;

const int N = 3 * 1e2 + 2;

int n, k;
int a[N][N];

int32_t main(){

  FIO
  //cout << fixed << setprecision(10);
  //freopen("input.txt", "r", stdin);
  //freopen("output.txt", "w", stdout);

  cin >> n >> k;
  rep(i,0,k){
    int d; cin >> d;
    rep(j,0,d){
      int s; cin >> s;
      a[s][i+1] = 1;
    }
  }
  int tot = 0;
  rep1(i,1,n){
    bool ok = 0;
    rep1(j,1,k) ok |= a[i][j];
    if(!ok) ++tot;
  }
  cout << tot << '\n';

	return 0;
}






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

int main() {
	string t; cin >> t; string s = t;
	int a =0; int b = 0;
	rep(i,t.length()) {
		if(t[i]=='?') {
			t[i] = 'D';
		}
	}
	cout << t << endl;
}


Measured memory_bytes: 3840
import java.util.Scanner;

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

        Scanner sc = new Scanner(System.in);
        int[] num = new int[3];
        int largest = 0;
        int index = 0;
        int sum = 0;

        for (int i = 0; i < 3; i++) {
            num[i] = sc.nextInt();
            if (num[i] > largest) {
                largest = num[i];
                index = i;
            }
        }
        int k = sc.nextInt();
        for (int i = 0; i < 3; i++) {
            if (i == index) {
                sum += num[i]* Math.pow(2, k);
            } else {
                sum += num[i];
            }
        }
        System.out.println(sum);
    }
}

Measured memory_bytes: 23124
fn get_input() -> String {
    let mut word = String::new();
    std::io::stdin().read_line(&mut word).unwrap();
    word.trim().to_owned()
}

fn main() {
	let (a,b) = {
	    let line = get_input();
	    let mut ab = line.split_whitespace();
	    let a:i32 = ab.next().unwrap().parse().unwrap();
	    let b:i32 = ab.next().unwrap().parse().unwrap();
	    (a,b)
	};

    let sum = a * b;

    if sum % 2 == 0 {
        println!("Even");
    } else {
        println!("Odd");
    }
}

Measured memory_bytes: 4352
def main():
    k = int(input())
    if k % 2 == 0:
        print(-1)
    else:
        a = 7
        if a % k == 0:
            print(1)
            exit()
        for i in range(2, k + 1):
            a = (10 * a + 7) % k
            if a % k == 0:
                print(i)
                exit()
        print(-1)





if __name__ == '__main__':
    main()


Measured memory_bytes: 9160
#include <iostream>
#include <cstdlib>
#include <list>
#include <map>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
 
int main(void)
{
    int64_t N, L[100];

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

    int ans = 0;
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < i; ++j)
        {
            for (int k = 0; k < j; ++k)
            {
                if ((L[i] == L[j]) || (L[j] == L[k]) || (L[k] == L[i])) continue;

                if (L[i] + L[j] > L[k])
                {
                    if (L[j] + L[k] > L[i])
                    {
                        if (L[k] + L[i] > L[j])
                        {
                            ++ans;
                        }
                    }

                }
            }
        }
    }

    cout << ans;
    return 0;
}


Measured memory_bytes: 3196
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <sstream>
#include <cmath>
#include <set>
using namespace std;

#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define REMOVE(Itr,n) (Itr).erase(remove((Itr).begin(),(Itr).end(),n),(Itr).end())
#define PB_VEC(Itr1,Itr2) (Itr1).insert((Itr1).end(),(Itr2).begin(),(Itr2).end())
typedef long long ll;

int main(){
    
    int N,L;
    cin>>N>>L;
    vector<string> s(N);
    REP(i,N)cin>>s[i];
    
    sort(s.begin(),s.end());
    
    REP(i,s.size())cout<<s[i];
    cout<<endl;
    
    return 0;
}

Measured memory_bytes: 256
// 2018, Sayutin Dmitry.

#include <bits/stdc++.h>

using std::cin;
using std::cout;
using std::cerr;

using std::vector;
using std::map;
using std::array;
using std::set;
using std::string;

using std::pair;
using std::make_pair;

using std::tuple;
using std::make_tuple;
using std::get;

using std::min;
using std::abs;
using std::max;

using std::unique;
using std::sort;
using std::generate;
using std::reverse;
using std::min_element;
using std::max_element;

#ifdef LOCAL
#define LASSERT(X) assert(X)
#else
#define LASSERT(X) {}
#endif

template <typename T>
T input() {
    T res;
    cin >> res;
    LASSERT(cin);
    return res;
}

template <typename IT>
void input_seq(IT b, IT e) {
    std::generate(b, e, input<typename std::remove_reference<decltype(*b)>::type>);
}

#define SZ(vec)         int((vec).size())
#define ALL(data)       data.begin(),data.end()
#define RALL(data)      data.rbegin(),data.rend()
#define TYPEMAX(type)   std::numeric_limits<type>::max()
#define TYPEMIN(type)   std::numeric_limits<type>::min()

#define pb push_back
#define eb emplace_back

int main() {
    std::iostream::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // code here
    int h = input<int>();
    int w = input<int>();
    int n = input<int>();
    
    vector<set<int>> by_y(h + 1);
    for (int i = 0; i != n; ++i) {
        int y = input<int>() - 1;
        int x = input<int>() - 1;

        by_y[y].insert(x);
    }
    
    int ans = h;
    int R = 0;

    if (by_y[1].count(0))
        ans = 1;
    
    for (int i = 1; i < h; ++i) {
        if (not by_y[i].count(R + 1))
            R += 1;

        if (not by_y[i + 1].empty() and *(by_y[i + 1].begin()) <= R) {
            ans = min(ans, i + 1);
        }
    }

    cout << ans << "\n";
    
    return 0;
}


Measured memory_bytes: 19072
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int N,w;
    cin >> N;
    long int u;
    u = 1000000000;
    w = 0;
    for(int i=0;i<N;i++){
        long int A;
        cin >> A;
        int s,t;
        s = 0;
        t = 0;
        while (s == 0){
            if (A%2 == 1){
                s++;
            }
            else{
                t++;
            }
            A /= 2;
        }
        if(t<u){
            w = t;
            u = t;
        } 
    }
    cout << w << endl;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;

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

		// 1行、2つ(複数)数字
		String[] ss0 = br.readLine().trim().split(" ", 0);
		long a = Long.parseLong(ss0[0]);
		long b = Long.parseLong(ss0[1]);
		long c = Long.parseLong(ss0[2]);
		
		//奇数がある
		if (isEnd(a, b, c)) { System.out.println(0); return; }
//		if ( a%2 == 1 ) { System.out.println(0); return; }
//		if ( b%2 == 1 ) { System.out.println(0); return; }
//		if ( c%2 == 1 ) { System.out.println(0); return; }

		//全部同じ
		if ((a==b)&&(b==c)) { System.out.println(-1); return; }

		long x;
		long y;
		long z;
		long count = 0L;
		
		do {
			x = (b+c)/2;
			y = (c+a)/2;
			z = (a+b)/2;
			count += 1;
			a=x;
			b=y;
			c=z;
		} while (isEnd(x,y,z)==false);

//		if (isEnd(x,y,z)) { System.out.println(count); return; }

        System.out.println(count);
        return;
    }
    //-----------------------------------------------------------------
    // Debug.Print
    static void dp(String s) {
		System.out.println(s);
	}
    static void dp(StringBuilder s) { dp(s.toString()); }
    static void dp(int i) { dp(String.valueOf(i)); }
    static void dp(long i) { dp(String.valueOf(i)); }

	static boolean isEnd(long a, long b, long c) {
		if ( a%2 == 1 ) { return true; }
		if ( b%2 == 1 ) { return true; }
		if ( c%2 == 1 ) { return true; }
		return false;
	}


}


Measured memory_bytes: 23124
import collections
def main():
    n = int(input())
    a = list(map(int,input().split()))
    cnt_ary = [0] * n

    for i,aa in enumerate(a):
        cnt_ary[aa-1] += 1


    tmp = 0
    ans_ary = [0] * n
    for i, cc in enumerate(cnt_ary):
        ans_ary[i] = cc * (cc-1)

    t = sum(ans_ary)
    ans = 0
    for i, aa in enumerate(a):
        ans = 0
        ans = t - ans_ary[aa-1]
        ans += (cnt_ary[aa-1] - 1) * (cnt_ary[aa-1] - 2)
        print(ans//2)



if __name__=='__main__':
    main()


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

int main()
{
    int N;
    cin >> N;
    vector<long long> cnt(100005, 0);
    for (int i = 0; i < N; i++)
    {
        int a;
        cin >> a;
        cnt[a]++;
    }
    long long total = 0LL;
    for (int i = 0; i < 100005; i++)
        total += i * cnt[i];

    int Q;
    cin >> Q;
    for (int i = 0; i < Q; i++)
    {
        int B, C;
        cin >> B >> C;
        total += (C - B) * cnt[B];
        cnt[C] += cnt[B];
        cnt[B] = 0;
        cout << total << endl;
    }
    return 0;
}

Measured memory_bytes: 3968
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a,b,c,d,p,sum1=0,sum2=0;
  cin >> a >> b >> c >> d >> p;
  sum1=a*p;
  if(p > c){
    p-=c;
    sum2+=p*d;
  }
  sum2+=b;
  if(sum1 > sum2){
    cout << sum2 << endl;
  } else{
    cout << sum1 << endl;
  }
  return 0;
}

Measured memory_bytes: 3056
/*
      author : nishi5451
      created: 11.08.2020 22:58:42
*/

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


int main(){
    int x,y,z;
    cin >> x >> y >> z;
    swap(x,y);
    swap(x,z);
    cout << x << " " << y << " " << z << endl;
    return 0;
}

Measured memory_bytes: 3580
#include <iostream>
#include <bitset>
#include <fstream>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <functional>
#include <cctype>
#include <list>
#include <limits>
//#include <boost/multiprecision/cpp_int.hpp>

const double EPS = (1e-10);


using namespace std;
using Int = long long;
//using namespace boost::multiprecision;

const Int MOD = 1000000007;

Int mod_pow(Int x, Int n) {
    Int res = 1;
    while(n > 0) {
        if(n & 1) res = (res * x) % MOD; //ビット演算(最下位ビットが1のとき)
        x = (x * x) % MOD;
        n >>= 1; //右シフト(n = n >> 1)
    }
    return res;
}

//最大公約数
template<typename T>
T gcd(T a, T b) {
    return b != 0 ? gcd(b, a % b) : a;
}

//最小公倍数
template<typename T>
T lcm(T a, T b) {
    return a * b / gcd(a, b);
}

int a[105];
int cnt[105];
vector<int> ans;
vector<vector<int>> groups;
set<pair<int, int>> s;

int main(){
    cin.tie(0); 
    int N; cin >> N;


    int divisor = 0;
    for (int i = 2; i < N; i++){
        if ((N+N*N)/2 % i == 0){
            divisor = i;
            break;
        }
    }
    vector<int> tmp;
    for (int i = 1; i <= N/2; i++){
        tmp.clear();
        if (N % 2){
            tmp.push_back(i);
            tmp.push_back(N-i);
        }else{
            tmp.push_back(i);
            tmp.push_back(N+1-i);
        }
        groups.push_back(tmp);
    }
    tmp.clear();
    if (N % 2) tmp.push_back(N);
    groups.push_back(tmp);
    for (int i = 0; i < groups.size(); i++){
        for (int j = 0; j < groups[i].size(); j++){
            for (int k = i+1; k < groups.size(); k++){
                for (int l = 0; l < groups[k].size(); l++){
                    int a = groups[i][j];
                    int b = groups[k][l];
                    if (b < a) swap(b, a);
                    s.insert({a, b});
                }
            }
        }
    }
    cout << s.size() << endl;
    for (auto itr = s.begin(); itr != s.end(); itr++){
        cout << itr->first << " " << itr->second << endl;
    }
    return 0;
}



Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;

vector<int> G[200002];
ii cnt[200002];
bitset<200002> ins;

int main() {
	int N, M;
	string s;
	cin >> N >> M >> s;
	auto cmp = [](int a, int b) {
		if ((cnt[a].first == 0 || cnt[a].second == 0) && (cnt[b].first == 0 || cnt[b].second == 0)) return a < b;
		if (cnt[a].first == 0 || cnt[a].second == 0) return true;
		if (cnt[b].first == 0 || cnt[b].second == 0) return false;
		else return a < b;
	};
	set<int, decltype(cmp)> S(cmp);
	for (int i = 0; i < N; ++i) {
		cnt[i] = ii(0, 0);
		S.insert(i);
	}
	while (M--) {
		int a, b;
		cin >> a >> b;
		--a, --b;
		if (a == b) {
			G[a].push_back(a);
			S.erase(a);
			s[a] == 'A' ? ++cnt[a].first : ++cnt[a].second;
			S.insert(a);
		}
		else {
			G[a].push_back(b);
			G[b].push_back(a);
			S.erase(a);
			S.erase(b);
			s[a] == 'A' ? ++cnt[b].first : ++cnt[b].second;
			s[b] == 'A' ? ++cnt[a].first : ++cnt[a].second;
			S.insert(a);
			S.insert(b);
		}
	}
	ins.set();
	while (!S.empty() && (cnt[*S.begin()].first == 0 || cnt[*S.begin()].second == 0)) {
		int u = *S.begin();
		S.erase(u);
		ins[u] = 0;
		for (auto& v : G[u]) {
			if (ins[v]) {
				S.erase(v);
				s[u] == 'A' ? --cnt[v].first : --cnt[v].second;
				S.insert(v);
			}
		}
	}
	
	cout << (S.empty() ? "No" : "Yes") << '\n';
}

Measured memory_bytes: 20868
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef std::vector<vector<int> > vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pi> vpi;
#define debugone(x) cerr << #x << " " << x << "\n"; cerr.flush();
#define debugtwo(x) cerr << #x << "-------------" << "\n";for(auto &it: x) cerr << it << " ";cerr << "\n"; cerr.flush();
#define debugthree(x, i, j) cerr << #x << "------------" << "\n";cerr << "from " << i << " to " << j << "\n";for(ll k=i; k<=j; k++) cerr << x[k] << " ";cerr << "\n"; cerr.flush();
#define trace1(x)                cerr << #x << ": " << x << endl;
#define trace2(x, y)             cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z)          cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define trace4(a, b, c, d)       cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
#define trace5(a, b, c, d, e)    cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
#define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;
 
const ll mod = 1e9 + 7;
const ll inf = 1e11 + 5;
const int MaxN = 2e5 + 5;

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

	string s;
	cin >> s;
	int n = s.length();
	for(int i = 0; i < n; i++){
		if(i & 1 && s[i] == 'R'){
			cout << "No" << endl;
			return 0;
		}
		if(!(i & 1) && s[i] == 'L'){
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
	return 0;
}	


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

#include <iostream>
#include <fstream>

#include <bits/stdc++.h>

#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
#define mp make_pair

using namespace std;

typedef long long int64;
typedef vector<int> vi;
typedef pair<int, int> ii;

const int64 MODULO = (int64) 1e9 + 7;

class TaskC {
 public:
  void solveOne(istream &in, ostream &out) {
    int n, a, b;
    in >> n >> a >> b;
    if (a > b) {
      int t = a;
      a = b;
      b = t;
    }
    vector<vector<int64>> diagSum(n + 1, vector<int64>(b));
    vector<vector<int64>> d(n + 1, vector<int64>(b));
    vector<int64> dPrefSum(n + 1);
    d[0][0] = 1;
    dPrefSum[0] = 1;
    diagSum[0][0] = 1;
    int64 finish = 0;
    for (int i = 1; i <= n; ++i) {
      dPrefSum[i] = dPrefSum[i - 1];
      for (int j = 1; j < b; ++j) {
        d[i][j] = d[i - 1][j - 1];
        if (i >= a + 1 && j >= a + 1) {
          d[i][j] += diagSum[i - a - 1][j - a - 1];
          if (d[i][j] >= MODULO) d[i][j] -= MODULO;
        }
        if (j == 1 && i >= 2) {
          d[i][j] += dPrefSum[i - 2];
          if (d[i][j] >= MODULO) d[i][j] -= MODULO;
          if (i > a) {
            d[i][j] -= dPrefSum[i - a - 1];
            if (d[i][j] < 0) d[i][j] += MODULO;
          }
        }
        diagSum[i][j] = d[i][j] + diagSum[i - 1][j - 1];
        if (diagSum[i][j] >= MODULO) diagSum[i][j] -= MODULO;
        dPrefSum[i] += d[i][j];
        if (dPrefSum[i] >= MODULO) dPrefSum[i] -= MODULO;
        if (n - i < a || j + n - i < b) {
          finish += d[i][j];
          if (finish >= MODULO) finish -= MODULO;
        }
      }
    }
    int64 res = 1;
    for (int i = 0; i < n; ++i) res = res * 2 % MODULO;
    res = (res + MODULO - finish) % MODULO;
    out << res << "\n";
  }

  void solve(std::istream &in, std::ostream &out) {
    int nt = 1;
    for (int it = 0; it < nt; ++it) {
      solveOne(in, out);
    }
  }
};


int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  TaskC solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  solver.solve(in, out);
  return 0;
}


Measured memory_bytes: 394432
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(true){
            String line = sc.nextLine();
            if(line.equals("0")){
                break;
            }
            int Sum = 0;
            for(int i = 0; i < line.length(); i++){
                Sum += line.charAt(i) - '0';
            }
            System.out.println(Sum);
        }
    }
}


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

int main() {
    int n;cin>>n;
    ll l[n+1];
    l[0]=2;
    l[1]=1;
    for (int i=2;i<=n;i++)
        l[i]=l[i-1]+l[i-2];
    cout<<l[n]<<endl;
    return 0;
}

Measured memory_bytes: 256
import collections
n=int(input())
l=list(map(int,input().split()))
a=[0]*n
b=[0]*n
for i in range(n):
  a[i]=i+1+l[i]
  b[i]=(i+1-l[i])
A=collections.Counter(a)
aa=A.most_common()
B=collections.Counter(b)

ans=0
for i in range(len(aa)):
  ans+=B[aa[i][0]]*aa[i][1]

print(ans)

Measured memory_bytes: 140452
#include<atcoder/all>
using namespace atcoder;

#include<bits/stdc++.h>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
#define rep(i,n) for(int i=0; i<(n); i++)

int RMQ_op(int a, int b) { return max(a, b); }
int RMQ_e() { return -1; }
struct RMQ_cmp { int tg; bool operator()(int v) const { return v < tg; } };

int main() {
    int N, Q; scanf("%d%d", &N, &Q);
    vector<int> A(N); rep(i, N) { int a; scanf("%d", &a); A[i] = a; }
    segtree<int, RMQ_op, RMQ_e> G(A);

    rep(q, Q) {
        int c; scanf("%d", &c);
        if (c == 1) {
            int x, v; scanf("%d%d", &x, &v); x--;
            G.set(x, v);
        }
        if (c == 2) {
            int l, r; scanf("%d%d", &l, &r); l--;
            printf("%d\n", G.prod(l, r));
        }
        if (c == 3) {
            int x, v; scanf("%d%d", &x, &v); x--;
            printf("%d\n", G.max_right(x, RMQ_cmp{ v }) + 1);
        }
    }

    return 0;
}

Measured memory_bytes: 6176
#include <stdio.h>
 
int main(void)
{
    char s[200];
    char p[100];
    int l,i = 0,j,k;

    scanf("%s\n",s);
    scanf("%s\n",p);

    while(s[i] != '\0') 
    {
    i++;
    l = i;
    }
    
    for(i = l; i < l*2; i++)
    {
    s[i] = s[i - l];
    }

    for(i = 0; i < l * 2; i++)
    {
        if(s[i] == p[0])
        {
            j = 0;
            k = i;

            while(s[k] == p[j])
            {
                j++;
                k++;

                if(p[j] == '\0')
                {
                    printf("Yes\n");
                    return 0;
                }
            }
        }
    }

    printf("No\n");
    return 0;
}


Measured memory_bytes: 2108
fun main(args: Array<String>) {
    val l1 = readLine()!!.split(" ").map{ it.toInt() }
    val b = readLine()!!.split(" ").map{ it.toInt() }
    var cnt = 0
    for (i in 0 until l1[0]) {
        val a = readLine()!!.split(" ").map { it.toInt() }
        var sum = 0;
        for (j in 0 until l1[1]) {
            sum += a[j]*b[j]
        }
        if (sum+l1[2] > 0) cnt++
    }
    println(cnt)
}

Measured memory_bytes: 38028
S = input()
ans = "AC"
count = 0
if S[0] == "A":
    if S[1].islower():
        if S.count("C") == 1:
            for i in range(2,len(S)):
                if S[i].islower():
                    count += 1
            if count != len(S) - 3:
                    ans = "WA"
        else:
            ans = "WA"
    else:
        ans = "WA"
else:
    ans = "WA"
if S[len(S)-1] == "C":
    ans = "WA"
print(ans)


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

typedef long long int ll;

void solve () {
    vector<ll> num(9);
    for (auto &i : num) cin >> hex >> i;
    num.push_back(0LL);

    vector<vector<bool> > bits_list(10, vector<bool>(33));
    auto itr = 0;
    for (auto i : num) {
        for (int j = 0; j < 32; j++) {
            bits_list[itr][j] = i % 2LL;
            i /= 2LL;
        }
        itr++;
    }

    int c = 0;
    for (int i = 0; i < 32; i++) {
        int count0 = c;
        int count1 = c;
        for (int j = 0; j < 8; j++) {
            count0 += bits_list[j][i] ^ false;
            count1 += bits_list[j][i] ^ true;
        }

        int tmp1 = (count0 + c) % 2;
        int tmp2 = (count1 + c) % 2;
        int tmp3 = bits_list[8][i];

        if (count0 % 2 == bits_list[8][i]) {
            bits_list[9][i] = 0;
            c = count0 / 2;
        } else {
            bits_list[9][i] = 1;
            c = count1 / 2;
        }
    }

    ll res = 0;
    c = 1;
    for (int i = 0; i < 32; i++) {
        res += bits_list[9][i] * c;
        c *= 2;
    }

    cout << hex << (int)res << endl;
}

int main() {
    int Q; cin >> Q;
    while (Q--) solve();

    return 0;
}

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

int main() {
  ll A, B, N;
  cin >> A >> B >> N;
  ll n = min(B, N);
  // ll ans = (A * n) / B;
  ll ans = 0;
  for (ll x = n - 2; x <= n; x++) {
    // ll x = i % B;
    ll y = (A * x) / B - A * (x / B);
    // ll y = (A * x) / B;
    ans = max(ans, y);
  }
  cout << ans << endl;
}


Measured memory_bytes: 3604
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

#define REP(i,n) for(int i = 0; i < n; i++)
#define ll long long
#define PI 3.141592653589

using namespace std;

int main(void){
    ll N, A;
    cin >> N;
    vector<int> vec;

    for(ll i = 1; i <= sqrt(N); i++){
        if(N % i == 0) vec.push_back(i);
    }
    
    if(vec.size() == 1) cout << N-1;
    else{
        A = vec.back();
        cout << A + N/A -2;
    }
    
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <random>
#include <functional>
#include <stack>
#include <iomanip>
#include <cassert>
using namespace std;
long long MOD = 1e9 + 7;

int main() {
	long long A, B, C;
	cin >> A >> B >> C;
	long long ans = 0;
	while (1) {
		if (A & 1 || B & 1 || C & 1) {
			cout << ans << endl;
			return 0;
		}
		if (A == B && B == C) {
			cout << -1 << endl;
			return 0;
		}
		long long p, q, r;
		p = (B + C) / 2;
		q = (C + A) / 2;
		r = (B + A) / 2;
		A = p;
		B = q;
		C = r;
		ans++;
	}
}

Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>

int main(void)
{
    double a, b, c;
    double area, lap, rad, h;
    double PI;

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

    PI = acos(-1);
    rad = c * PI / 180;
    area = a * b * 0.5 * sin(rad);
    printf("%lf\n", area);

    lap = (a * a + b * b - 2 * a * b * cos(rad));
    printf("%lf\n", sqrt(lap) + a + b);

    h = area * 2 / a;
    printf("%lf", h);

    return (0);
}



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


void solve(long long N, std::vector<long long> d){
  sort(d.begin(), d.end());
  auto x = unique(d.begin(), d.end());
  d.erase(x, d.end());
  cout << d.size() << endl;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long N;
  scanf("%lld",&N);
  std::vector<long long> d(N);
  for(int i = 0 ; i < N ; i++){
    scanf("%lld",&d[i]);
  }
    solve(N, std::move(d));
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<numeric>
#include<iomanip>
#include<deque>
#include<tuple>
#include<queue>
#include<map>
#include<cstdint>
#include<unordered_map>
#include<boost/multiprecision/cpp_int.hpp>


#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define vi vector<int>
#define all(x) (x).begin(),(x).end()
#define Endl endl
#define F first
#define S second

namespace mp = boost::multiprecision;

using cpp_int = mp::cpp_int;
using ll = long long;
using namespace std;


int main() {
	int n;
	cin >> n;
	vector<int>C(n), S(n), F(n);
	rep(i, n-1) {
		cin >> C[i] >> S[i] >> F[i];
	}
	rep(i, n) {
		int time = S[i] + C[i];
		FOR(j, i+1, n - 1) {
			int buffer = 0;
			if (time > S[j]) {
				time -= S[j];
				if (time % F[j] == 0) {
					buffer = time / F[j];
				}
				else {
					buffer = time / F[j] + 1;
				}
				buffer *= F[j];
			}
			time = buffer + S[j] + C[j];
		}
		cout << time << endl;
	}
}



Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <iomanip>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <cstdint>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
#define MP make_pair
#define PB push_back
#define inf 1000000007
#define rep(i,n) for(int i = 0; i < (int)(n); ++i)
#define all(x) (x).begin(),(x).end()

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}
 
template<class T> inline bool chmax(T &a, T b){
    if(a<b){
        a = b;
        return true;
    }
    return false;
}

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

int main(){
    ll a,b,c;
    cin >> a >> b >> c;
    if(a+b>=c){
        cout << "No" << endl;
    }else if((c-a-b)*(c-a-b) > 4*a*b){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}

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

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

    void solve(Scanner sc) {
        int n = sc.nextInt();
        int[] primePow = new int[n + 1];
        Arrays.fill(primePow, 1);
        for (int i = 2; i <= n; i++) {
            int tmp = i;
            for (int j = 2; tmp != 1; j++) {
                while (tmp % j == 0) { 
                    primePow[j]++;
                    tmp /= j;
                }
            }
        }
        long ans = 1;
        for (int i = 0; i < n +1; i++) {
            ans = (ans * primePow[i]) % (1_000_000_000 + 7);
        }
        System.out.println(ans);
    }
}


Measured memory_bytes: 22996
/*   _/                _/                 _/_/_/   _/
  _/_/_/_/   _/_/   _/_/_/_/   _/_/    _/       _/_/
   _/     _/    _/   _/     _/    _/  _/_/_/     _/
  _/     _/    _/   _/     _/    _/  _/    _/   _/
   _/_/   _/_/       _/_/   _/_/      _/_/     _/ */
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<set>
#include<map>
#include<queue>
#include<vector>
using namespace std;
using ll=long long;
const int MOD=1e9+7;
const double pi=3.14159265358979323846;
const int inf=2e9;
const ll INF=1e18;
using P=pair<int,int>;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int main() {
  cin.tie(0),cout.tie(0);
  ios::sync_with_stdio(false);
  int q,l,r,x[100005]={};
  bool f[100005]={};
  cin >> q;
  for(int i=2; i<=100000; i++) {
    if(!f[i]) {
      for(int j=i*2; j<=100000; j+=i) {
        f[j]=true;
      }
    }
  }
  for(int i=3; i<=100000; i++) {
    if(!f[i]&&!f[(i+1)/2]) {
      x[i]=1;
    }
  }
  for(int i=1; i<=100000; i++) {
    x[i]+=x[i-1];
  }
  while(q--) {
    cin >> l >> r;
    cout << x[r]-x[l-1] << "\n";
  }
}

Measured memory_bytes: 1152
/*
*          Name : chaitanya
*
*     Institute : ANITS,Visakhapatnam
*
*/
#include<cstdio>
#include<iostream>
#include<sstream>
#include<fstream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<complex>
#include<cstring>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<bitset>
#include<numeric>
#include<limits>
#include<climits>
#include<cfloat>
#include<functional>
#include<iterator>
#include <random>
#define infy  1000000000
#define all(x) begin(x),end(x)
#define ll long long int
#define ff first
#define ss second
#define pb push_back
const ll m = 1000000007;
#pragma GCC optimization ("O3")
const int N = 1000010;
using namespace std;
vector<string> vec_splitter(string s) {
  s += ',';
  vector<string> res;
  while(!s.empty()) {
    res.push_back(s.substr(0, s.find(',')));
    s = s.substr(s.find(',') + 1);
  }
  return res;
}
void debug_out(
vector<string> __attribute__ ((unused)) args,
__attribute__ ((unused)) int idx, 
__attribute__ ((unused)) int LINE_NUM) { cerr << endl; } 
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
  if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";
  stringstream ss; ss << H;
  cerr << args[idx] << " = " << ss.str();
  debug_out(args, idx + 1, LINE_NUM, T...);
}
#ifndef ONLINE_JUDGE
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define debug(...) 42
#endif

ll f[2000010];

ll lcm(ll a,ll b)
{
  return (a*b)/__gcd(a,b);
}
ll binpow(ll a, ll b) {
     ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}
 
ll find_ncr(ll n, ll r)
{
    ll m1=max(r,n-r);
    ll i,j,s,d=1,k;
    s=1;
 
    for(i=m1+1;i<=n;i++)
    {
        s=((s%m)*(i%m))%m;
    }
 
    m1=min(r,n-r);
 
    for(i=1;i<=m1;i++)
    {
        k=binpow(i,m-2);
        d=((d%m)*(k%m))%m;
    }
 
    k=(s%m*(d%m))%m;
 
    return k;
}

int main()
{
  // int x = -1, y = 10000;
  // double z = 0.2;
  // string s2 = "beginner1010";
  // long long b = 1LL << 60;
    
  // // debug(x, y, z, s, b);
    
  // double aux = 1010.0;
  // string code = "code";
    
  // debug(code + "forces",-aux / 10 * 2.3);
  // freopen("input.txt","r",stdin);
  // freopen("output.txt","w",stdout);
  //ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  ll n;
  cin >> n;
  queue<ll>q;
  for (ll i = 1; i <= 9; ++i)
  {
    q.push(i);
  }
  ll c = 0,a;
  for (int i = 0; i < n; ++i)
  {
    a = q.front();
    if (i == n-1)
    {
      cout << a;
      return 0;
    }
    q.pop();
    a = a*10+a%10;
    if(a%10 != 0) q.push(a-1);
    q.push(a);
    if(a%10 != 9) q.push(a+1);
  }
  return 0;
}



Measured memory_bytes: 1792
#include<stdio.h>
int main(void)
{
	int i,m,n,x,y;
	scanf("%d",&n);
	while(n!=0) {
		m=n/4;
		y=0;
		for(i=1;i<=m;i++) {
			scanf("%d",&x);
			y+=x;
		}
		printf("%d\n",y);
	scanf("%d",&n);
	}
	return 0;
}

Measured memory_bytes: 600
import java.util.Scanner;

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

	String s = scan.next();
	String t = scan.next();

	int flag = -1;
	for(int i = 0; i < s.length(); i++){
	    if(s.equals(t)){
		flag = 1;
		break;
	    }
	    char c = s.charAt(s.length()-1);
	    String C = String.valueOf(c);
	    s = s.substring(0, s.length()-1);
	    s = C+s;
	}

	if(flag == 1){
	    System.out.println("Yes");
	}else{
	    System.out.println("No");
	}
    }
}


Measured memory_bytes: 22740
#include <stdio.h>

int main(){
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
int count;
if(a!=b && b!=c && c!=a) count=3;
else if(a==b && c!=a) count=2;
else if(b==c && a!=b) count=2;
else if(c==a && b!=c) count=2;
else count=1;
printf("%d\n", count);
return 0;
}

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

using namespace std;

#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define repr(i, n) REPR(i, n, 0)
#define REPR(i, s, e) for(int i=(int)(s-1); i>=(int)(e); i--)
#define pb push_back
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()
#define fi first
#define se second

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int INF = 1e9;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    sort(all(a));
    map<int, int> mp;
    rep(i, n) mp[a[i]]++;
    bool f = true;
    if (mp.size() != 3) {
        if (mp.size() == 1) {
            if (mp.begin()->fi != 0) f = false;
        } else if (mp.size() == 2) {
            if (mp.begin()->fi != 0) f = false;
            else {
                vi u, v;
                for (auto && p : mp) {
                    u.pb(p.fi);
                    v.pb(p.se);
                }
                if(u[0] == 0 && v[0]*2 == v[1]);
                else f = false;
            }
        } else f = false;
    } else {
        vi u, v;
        for (auto && p : mp) {
            u.pb(p.fi);
            v.pb(p.se);
        }
        if (((u[0]^u[1])^u[2]) != 0) f = false;
        if (v[0] == v[1] & v[1] == v[2]);
        else f = false;
    }
    string yes = "Yes", no = "No";
    cout << (f ? yes : no) << endl;
    return 0;
}

Measured memory_bytes: 4224
#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<set>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)

using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<ll, ll, ll> tpl;


template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
	return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T& t, const V& v) { t = v; }
template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T& t, const V& v) {
	for (auto& e : t) fill_v(e, v);
}


#define ARRAY_MAX 100005
const int INF = 1e9 + 7;
const ll MOD = 1e9 + 7;

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




/******************************************************************************************/



//素数判定
bool is_prime(ll n) {
	for (ll i = 2; i*i <= n; i++) {
		if (n % i == 0) {
			return false;
		}
	}
	return n != 1;//1の場合は除外
}



//約数の列挙
template<typename T>
vector<T> divisor(T n) {
	vector<T> res;
	for (T i = 1; i * i <= n; i++) {
		if (n % i == 0) {
			res.push_back(i);
			if (i != n / i) {
				res.push_back(n / i);
			}
		}
	}
	return res;
}




//ユークリッド互除法
template<typename T>
T gcd(T x, T y) {

	if (y == 0) {
		return x;
	}
	else {
		return gcd(y, x % y);
	}
}





int main() {

	int mp[5][5];
	for (int i = 0; i < 3; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			cin >> mp[i][j];
		}
	}

	int a[5] = {}, b[5] = {};

	for (int a1 = 0; a1 <= mp[0][0]; a1++)
	{
		a[0] = a1;
		b[0] = mp[0][0] - a1;

		for (int a2 = 0; a2 <= mp[1][1]; a2++)
		{
			a[1] = a2;
			b[1] = mp[1][1] - a2;

			for (int a3 = 0; a3 <= mp[2][2]; a3++)
			{
				a[2] = a3;
				b[2] = mp[2][2] - a3;

				bool flag = true;
				for (int i = 0; i < 3; i++)
				{
					for (int j = 0; j < 3; j++)
					{
						flag &= (mp[i][j] == a[i] + b[j]);
					}

				}

				if (flag) {
					cout << "Yes" << endl;
					return 0;
				}

			}
		}
	}

	cout << "No" << endl;








	
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
double calc(double a,double b,double c){
	double s=(a+b+c)/2;
	return sqrt(s*(s-a)*(s-b)*(s-c));
}
int main(){
	int a,b,c;
	while(~scanf("%d%d%d",&a,&b,&c)){
		printf("%.12f\n",calc(a,b,b)+calc(b,0.5*(b+c),0.5*(b+c))*2);
	}
}

Measured memory_bytes: 1048
import sys

sys.setrecursionlimit(10 ** 6)


def dfs(links, n, k, v, p):
    height_from_leaf = 0
    cut_count = 0
    for u in links[v]:
        if u == 0:
            continue
        hgt, cut = dfs(links, n, k, u, v)
        height_from_leaf = max(height_from_leaf, hgt)
        cut_count += cut
    height_from_leaf += 1
    if p != 0 and height_from_leaf == k:
        height_from_leaf = 0
        cut_count += 1
    return height_from_leaf, cut_count


n, k, *aaa = map(int, sys.stdin.buffer.read().split())
links = [set() for _ in range(n)]
for i, a in enumerate(aaa):
    a -= 1
    links[a].add(i)
_, ans = dfs(links, n, k, 0, 0)
if aaa[0] != 1:
    ans += 1

print(ans)


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

using namespace std;


void solve() {
    int n, A, B;
    cin >> n >> A >> B;
    vector<int> a(n+2);
    a[0] = 0; a[n+1] = n+1;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    vector<long long> dp(n+2, 1ll<<60);
    dp[0] = 0;
    for (int i = 1; i <= n+1; i++) {
        int cnt = 0;
        for (int j = i-1; j >= 0; j--) {
            if (a[j] < a[i]) {
                dp[i] = min(dp[i], dp[j] + 1ll*cnt*A + 1ll*(i-1-j-cnt)*B);
            } else {
                cnt++;
            }
        }
    }
    cout << dp[n+1];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    cout << endl;
}


Measured memory_bytes: 384
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
static const int MAX=10000;
static const int INFTY=(1<<20);
static const int WHITE=0;
static const int GRAY=1;
static const int BLACK=2;

int n;
vector<pair<int,int> >adj[MAX];

void dijkstra(){
    priority_queue<pair<int,int> >PQ;
    int dtw[MAX],color[MAX];

    for(int i=0;i<n;i++){
        dtw[i]=INFTY;
        color[i]=WHITE;
    }

    dtw[0]=0;
    PQ.push(make_pair(0,0));
    color[0]=GRAY;

    while(!PQ.empty()){
        pair<int,int>f=PQ.top();PQ.pop();
        int u= f.second;

        color[u]=BLACK;


        if(dtw[u]<f.first*(-1))continue;

        for(int j=0;j<adj[u].size();j++){
            int v=adj[u][j].first;
            if(color[v]==BLACK)continue;
            if(dtw[v]>dtw[u]+adj[u][j].second){
                dtw[v]=dtw[u]+adj[u][j].second;

                PQ.push(make_pair(dtw[v]*(-1),v));
                color[v]=GRAY;
            }
        }
    }
    
    for(int i=0;i<n;i++){
        cout<<i<<" "<<(dtw[i]==INFTY ? -1 : dtw[i]) <<endl;
    }
}

int main(){
    int k,u,v,c;

    cin>>n;
    for(int i=0;i<n;i++){
        cin>>u>>k;
        for(int j=0;j<k;j++){
            cin>>v>>c;
            adj[u].push_back(make_pair(v,c));
        }
    }

    dijkstra();

    return 0;
}


Measured memory_bytes: 8080
#include <iostream>
#include <cstring>
#include <map>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <set>
#include <vector>
#include <queue>
#include <list>
#include <numeric>
#include <stdio.h>
#include <string>
#include <cstdlib>
#include <math.h>
#include <stack>
#include <climits>
#include <bitset>
#include <utility>


using namespace std;
typedef long long ll;
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; }
// const ll INF = 1LL <<60;
const int INF = 10000;

//最大公約数
ll gcd(ll x, ll y) {
  ll tmp = 0;
  if (x < y){
    tmp=x;
    x=y;
    y=tmp;
  }
  while (y > 0) {
    ll r = x % y;
    x = y;
    y = r;
  }
  return x;
}

//最大公倍数
ll lcm(ll x,ll y){
  return x/gcd(x,y)*y;
}

const int MAX = 510000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}


//階乗
ll kaijo(ll k){
    ll sum = 1;
    for (ll i = 1; i <= k; ++i)
    {
        sum *= i;
        sum%=1000000000+7;
    }
    return sum;
}

//for(int i = ; i < ; i++){}

ll lmax(ll s,ll t){
  if(s>t){
    return s;
  }
  else{
    return t;
  }
}

ll lmin(ll s,ll t){
  if(s<t){
    return s;
  }
  else{
    return t;
  }
}
// ここから開始
int main(){
  int n;
  cin>>n;
  ll a[n],b[n];
  for(int i = 0; i < n; i++) {
    cin>>b[i];
  }
  sort(b,b+n);
  for(int i = 0; i < n; i++) {
    if(i == 0) a[i]=b[i];
    else a[i] = a[i-1] + b[i];
  }
  // for(int i = 0; i < n; i++) cout<<a[i]<<" ";
  // cout<<endl;
  // for(int i = 0; i < n; i++) cout<<b[i]<<" ";
  // cout<<endl;
  int ansflg = 0;
  for(int i = 0; i < n-1; i++){
    // cout<<a[i]<<" "<<b[i]<<endl;
    if(a[i]*2<b[i+1]){
      ansflg = i+1;
    }
  }
  cout<<n-ansflg<<endl;
  return 0;
}



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

int main()
{
  int a, b;
  cin >> a >> b;
  int max = a + b;
  if (a - b > max)
  {
    max = a - b;
  }
  if (a * b > max)
  {
    max = a * b;
  }
  cout << max << endl;
}


Measured memory_bytes: 256
def solve():
    S = input()
    cnt = 0
    ans = 0
    for s in S:
        if s == 'R':
            cnt += 1
        else:
            ans = max(ans,cnt)
            cnt = 0
    else:
        ans = max(ans,cnt)
    
    print(ans)

if __name__ == '__main__':
    solve()

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

int main() {
    int N, W;
    cin >> N >> W;
    int v[N + 1], w[N + 1];
    for (int i = 0; i < N; ++i) cin >> v[i] >> w[i];
    int dp[N + 1][W + 1];
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j <= W; ++j) {
            if (j < w[i]) {
                dp[i + 1][j] = dp[i][j];
            } else {
                dp[i + 1][j] = max(dp[i][j], dp[i + 1][j - w[i]] + v[i]);
            }
        }
    }
    cout << dp[N][W] << endl;

    return 0;
}


Measured memory_bytes: 7056
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE TupleSections #-}
{-# LANGUAGE ExplicitForAll #-}
{-# LANGUAGE LambdaCase #-}
{-# LANGUAGE MultiWayIf #-}
{-# LANGUAGE Unsafe #-}
{-# LANGUAGE RecordWildCards #-}
{-# LANGUAGE FlexibleContexts #-}

import Data.Bits
import Data.List
import qualified Data.ByteString.Char8 as BS
import qualified Data.ByteString.Lazy.Char8 as BSL
import Data.IntMap.Strict (IntMap)
import qualified Data.IntMap.Strict as IMS
import Data.IntSet (IntSet)
import qualified Data.IntSet as IS
import qualified Data.Sequence as Seq
import Data.Sequence (Seq)
import qualified Data.Array.IArray as A
import qualified Data.Array.MArray.Safe as A
import qualified Data.Array.MArray as A
import Data.Array (Array)
import Data.Array.Unboxed (UArray)
import Data.Array.IArray (IArray)
import Data.Array.MArray.Safe (MArray)
import Data.Array.IO.Safe (IOArray, IOUArray)
import Data.Array.ST.Safe (STArray, STUArray, runSTArray, runSTUArray)
import qualified Data.Vector as V
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM
import Control.Monad
import Control.Monad.ST
-- import Control.Monad.ST.Safe
import Control.Applicative
import Data.Maybe
import Data.Tuple
import Data.Ord
import Control.Monad.State.Strict
import Data.Int
import System.IO
import Data.Function
import Control.Monad.Primitive
import qualified Data.Vector.Primitive.Mutable as VPM
import qualified Data.Vector.Generic.Mutable as VGM
import Data.STRef


rInt :: StateT BSL.ByteString Maybe Int
rInt = StateT $ BSL.readInt . BSL.dropWhile (<'!')


main :: IO ()
main = do
  [h,w] <- map read . words <$> getLine
  bss <- BSL.lines <$> BSL.getContents
  let ass = V.fromListN h $ map (VU.map (=='.') . VU.unfoldrN w BSL.uncons) bss
  print $ query h w ass

{-# INLINE query #-}
query :: Int -> Int -> V.Vector (VU.Vector Bool) -> Int
query h w
  = (VU.last .)
  $ V.foldl'
     (\vecAbove as ->
        VU.postscanl' (\left (above,a) ->
                         if | not a -> 0
                            | left + above < modulus -> left + above
                            | otherwise -> left + above - modulus)
          0 $ VU.zip vecAbove as)
  $ VU.cons 1 $ VU.replicate (w-1) 0

modulus :: Int
modulus = 10^9 + 7


Measured memory_bytes: 2044