結果
問題 | No.37 遊園地のアトラクション |
ユーザー |
![]() |
提出日時 | 2022-05-23 01:37:53 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,072 ms / 5,000 ms |
コード長 | 2,605 bytes |
コンパイル時間 | 878 ms |
コンパイル使用メモリ | 95,140 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-20 13:00:26 |
合計ジャッジ時間 | 2,973 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 27 |
ソースコード
//Yukicoder//Q37 遊園地のアトラクション////二次元可変配列//vector <vector <int>> mass;//vector <vector <int>> memo;//#include "stdafx.h"#include <iostream>#include <vector>#include <list>//list#include <set> //tree#include <map> //連想配列#include <unordered_set> //hash#include <unordered_map> //hash#include <algorithm>#include <iomanip>using namespace std;typedef unsigned long long ULL;typedef signed long long SLL;#define START (0)#define RIGHT (1)#define UP (2)#define LEFT (3)#define DOWN (4)#define DATA_MAX (1000000)#define FMAX(a,b) ((a)>(b)?(a):(b))#define FMIX(a,b) ((a)<(b)?(a):(b))vector <vector <SLL>> memo2;vector<SLL> memo1;SLL N, D, H ,A, B, T;typedef struct CAR {int c;int v;}CAR;CAR car[20];//昇順int compare(const CAR * a, const CAR *b){if (a->c > b->c)return (1);else if (a->c < b->c)return (-1);return (0);}// N種類までのアトラクションに乗れた場合に、T時間の時点での最大満足度を保存してく// dp[N][T]int dp[20][10100];void debug_print( void ){cout << "---" << endl;for (int i = 0; i < N; i++){for (int j = 1; j <= T; j++)cout << dp[i][j] << ",";cout << endl;}}int main(){//float min = INFINITY;cin >> T;cin >> N;for (int i = 0; i < N; i++){cin >> car[i].c;}for (int i = 0; i < N; i++){cin >> car[i].v;}//アトラクションの時間の昇順にソートqsort(car, N, sizeof(CAR), (int(*)(const void*, const void*))compare);/*for (int i = 0; i < N; i++)cout << "c=" << car[i].c << ",v=" << car[i].v << endl;*/int v = car[0].v;int first = 1;//最初の1行for (int t = 1; t <= T; t++){if (t >= car[0].c){if (((t % car[0].c) == 0) && (first==0)){car[0].v >>= 1;v += car[0].v;}dp[0][t] = v;first = 0;}}//2行目以降for (int n = 1; n < N; n++){for (int t = 1; t <= T; t++){//debug_print();if (t >= car[n].c){int curr=0;int v0 = car[n].v;int vv = car[n].v;int mmax = 0;int m = 1;// 1つ前の満足度と今回のものを足した時の満足度(1回以上)を比較do {curr = dp[n - 1][t - car[n].c*m] + v0;if (mmax < curr)mmax = curr;m++;vv /= 2;v0 += vv;} while (t > (car[n].c * m) );dp[n][t] = (mmax > dp[n - 1][t]) ? mmax : dp[n - 1][t];}else{dp[n][t] = dp[n - 1][t];}}}cout << dp[N-1][T] << endl;//getchar();return 0; //end}